HackerEarth Productive productivity problem solution

In this HackerEarth Productive productivity problem solution Little Jhool is a very lenient teaching assistant in his college. He doesn’t like cutting the marks of students, so obviously, every student in his tutorial loves him. Specially, the girls. They’re crazy about him.

But anyway, the teacher has got to know about the leniency of Jhool while giving marks, so this time in exam, he decides to give a different exam paper to every single student to check how well have the students been taught by Jhool. Now, Little Jhool knows the strong and weak topics of every single student, so he wants to maximize the total marks obtained by students in his tutorial.

You are given the number of students in Jhool’s tutorial, denoted by n – n also being the number of different exam papers – that is, one for every student. Every student will get only one exam paper to solve. You are further given a matrix, (n x n) denoting the marks every student will get if he attempts a particular exam paper. You’ve to help Jhool figure out a way by which he could maximize the total score obtained by his entire class.

HackerEarth Productive productivity problem solution.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define ND 30000
#define ED 1000000
#define INF 1000000
#define pii pair<int,int>
#define f_in(st) freopen(st,"r",stdin);
#define f_out(st) freopen(st,"w",stdout);
int n,k,m,eg_no,st,en,rs,fl,mx;
int to[ED],nx[ED],cap[ED],cst[ED],last[ND],ds[ND],pr[ND],pr_i[ND];
void init()
{
    eg_no=0;
    memset(last,-1,sizeof(last));
}
void add_edge(int u,int v,int cp,int r_cp,int cs,int r_cs)
{
    to[eg_no]=v;cap[eg_no]=cp;cst[eg_no]=cs;nx[eg_no]=last[u];last[u]=eg_no++;
    to[eg_no]=u;cap[eg_no]=r_cp;cst[eg_no]=r_cs;nx[eg_no]=last[v];last[v]=eg_no++;
}
int bellman()
{
    for(int i=0;i<ND;i++) ds[i]=INF;
    memset(pr,-1,sizeof(pr));
    memset(pr_i,-1,sizeof(pr_i));
    queue<int>q;
    int mrk[ND];
    memset(mrk,0,sizeof(mrk));
    q.push(st);mrk[st]=1;ds[st]=0;
    while(!q.empty())
    {
        int p=q.front();q.pop();
        mrk[p]=0;
        for(int i=last[p];i>=0;i=nx[i])
        {
            int t=to[i];
            if(cap[i]<=0) continue;
            if(ds[t]>ds[p]+cst[i])
            {
                ds[t]=ds[p]+cst[i];
                pr[t]=p;pr_i[t]=i;
                if(mrk[t]==0){ mrk[t]=1;q.push(t); }
            }
        }
    }
    //cout<<ds[en]<<"-n";
    if(ds[en]==INF) return 0;
    int x=en,mn=10000;
    while(pr[x]!=-1){ mn=min(mn,cap[pr_i[x]]);x=pr[x]; }
    //cout<<"nn";
    x=en;
    while(pr[x]!=-1)
    {
        int z=pr_i[x];
        cap[z]-=mn;cap[z^1]+=mn;
        x=pr[x];
    }
    rs+=ds[en];
    return mn;
}    
int maxflow()
{
    rs=0;
    int ans=0;
    while(1)
    {
        int res=bellman();
        if(res==0) break;
        ans+=res;
    }
    //cout<<"ans = "<<ans<<"n";
    return rs;
}   
int main()
{
    //f_in("sample_in.txt");
    //f_out("sample_out.txt");
    int tt;
    cin>>tt;
    for(int ii=1;ii<=tt;ii++)
    {
        init();
        cin>>n;
        st=2*n;en=2*n+1;
        for(int i=0;i<n;i++) add_edge(st,i,1,0,0,0);
        for(int i=0;i<n;i++) add_edge(n+i,en,1,0,0,0); 
        for(int i=0;i<n;i++)
        {
          for(int j=0;j<n;j++)
          {
            int x;
            cin>>x;
            add_edge(i,n+j,1,0,-x,x);
          }
        }
        cout<<0-maxflow()<<"n";
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

#define N 101             //max number of vertices in one part
#define INF 100000000    //just infinity

int cost[N][N];          //cost matrix
int n, max_match;        //n workers and n jobs
int lx[N], ly[N];        //labels of X and Y parts
int xy[N];               //xy[x] - vertex that is matched with x,
int yx[N];               //yx[y] - vertex that is matched with y
bool S[N], T[N];         //sets S and T in algorithm
int slack[N];            //as in the algorithm description
int slackx[N];           //slackx[y] such a vertex, that
// l(slackx[y]) + l(y) - w(slackx[y],y) = slack[y]
int prv[N];             //array for memorizing alternating paths


void init_labels()
{
  memset(lx, 0, sizeof(lx));
  memset(ly, 0, sizeof(ly));
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++)
      lx[x] = max(lx[x], cost[x][y]);
}

void update_labels()
{
  int x, y, delta = INF;             //init delta as infinity
  for (y = 0; y < n; y++)            //calculate delta using slack
    if (!T[y])
      delta = min(delta, slack[y]);
  for (x = 0; x < n; x++)            //update X labels
    if (S[x]) lx[x] -= delta;
  for (y = 0; y < n; y++)            //update Y labels
    if (T[y]) ly[y] += delta;
  for (y = 0; y < n; y++)            //update slack array
    if (!T[y])
      slack[y] -= delta;
}

void add_to_tree(int x, int prevx) 
  //x - current vertex,prevx - vertex from X before x in the alternating path,
  //so we add edges (prevx, xy[x]), (xy[x], x)
{
  S[x] = true;                    //add x to S
  prv[x] = prevx;                //we need this when augmenting
  for (int y = 0; y < n; y++)    //update slacks, because we add new vertex to S
    if (lx[x] + ly[y] - cost[x][y] < slack[y])
    {
      slack[y] = lx[x] + ly[y] - cost[x][y];
      slackx[y] = x;
    }
}


void augment()                         //main function of the algorithm
{
  if (max_match == n) return;        //check wether matching is already perfect
  int x, y, root;                    //just counters and root vertex
  int q[N], wr = 0, rd = 0;          //q - queue for bfs, wr,rd - write and read
  //pos in queue
  memset(S, false, sizeof(S));       //init set S
  memset(T, false, sizeof(T));       //init set T
  memset(prv, -1, sizeof(prv));    //init set prev - for the alternating tree
  for (x = 0; x < n; x++)            //finding root of the tree
    if (xy[x] == -1)
    {
      q[wr++] = root = x;
      prv[x] = -2;
      S[x] = true;
      break;
    }

  for (y = 0; y < n; y++)            //initializing slack array
  {
    slack[y] = lx[root] + ly[y] - cost[root][y];
    slackx[y] = root;
  }

  //second part of augment() function
  while (true)                                                        //main cycle
  {
    while (rd < wr)                                            //building tree with bfs cycle
    {
      x = q[rd++];                                             //current vertex from X part
      for (y = 0; y < n; y++)                   //iterate through all edges in equality graph
        if (cost[x][y] == lx[x] + ly[y] &&  !T[y])
        {
          if (yx[y] == -1) break;                //an exposed vertex in Y found, so
          //augmenting path exists!
          T[y] = true;                                        //else just add y to T,
          q[wr++] = yx[y];                            //add vertex yx[y], which is matched
          //with y, to the queue
          add_to_tree(yx[y], x);                  //add edges (x,y) and (y,yx[y]) to the tree
        }
      if (y < n) break;                                           //augmenting path found!
    }
    if (y < n) break;                                               //augmenting path found!

    update_labels();                       //augmenting path not found, so improve labeling
    wr = rd = 0;                
    for (y = 0; y < n; y++)        
      //in this cycle we add edges that were added to the equality graph as a
      //result of improving the labeling, we add edge (slackx[y], y) to the tree if
      //and only if !T[y] &&  slack[y] == 0, also with this edge we add another one
      //(y, yx[y]) or augment the matching, if y was exposed
      if (!T[y] &&  slack[y] == 0)
      {
        if (yx[y] == -1)              //exposed vertex in Y found - augmenting path exists!
        {
          x = slackx[y];
          break;
        }
        else
        {
          T[y] = true;                                        //else just add y to T,
          if (!S[yx[y]])    
          {
            q[wr++] = yx[y];           //add vertex yx[y], which is matched with
            //y, to the queue
            add_to_tree(yx[y], slackx[y]);          //and add edges (x,y) and (y,
            //yx[y]) to the tree
          }
        }
      }
    if (y < n) break;                                               //augmenting path found!
  }

  if (y < n)                                               //we found augmenting path!
  {
    max_match++;                                                    //increment matching
    //in this cycle we inverse edges along augmenting path
    for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
    {
      ty = xy[cx];
      yx[cy] = cx;
      xy[cx] = cy;
    }
    augment();                             //recall function, go to step 1 of the algorithm
  }
}//end of augment() function



int hungarian()
{
  int ret = 0;                      //weight of the optimal matching
  max_match = 0;                    //number of vertices in current matching
  memset(xy, -1, sizeof(xy));    
  memset(yx, -1, sizeof(yx));
  init_labels();                    //step 0
  augment();                        //steps 1-3
  for (int x = 0; x < n; x++)       //forming answer there
    ret += cost[x][xy[x]];
  return ret;
}

int main () {
  int tc;
  cin >> tc;
  while (tc--)
  {
    cin >> n;
    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        scanf("%d",&cost[i][j]);
    long long ans = hungarian();
    cout << ans << endl;
  }
  return 0;
}

coding problems