HackerEarth Bruce and the Chocolates problem solution

In this HackerEarth Bruce and the Chocolates problem solution Early this morning, I found our little Bruce sitting on a bench alone in the park. I sat beside him to ask where has he dropped his smile this morning?

Bruce: "Oh, Hi.. I love chocolates. (Who doesn't? ). It's chocolate day in school, and I forgot! Everyone is bringing chocolates. We play a game on this day, where the teacher makes pair of students and the students in each pair share their chocolates. I will have to go empty handed and hence, won't get paired :( "

"That's okay ,Bruce. You can ask your friends to share with you"

Bruce: " I did a smarter thing, I talked to my Mathematics teacher. I'm her favorite! She agreed that I could do the pairing! and from every pair , I could take 'x' number of chocolates, where x is the greatest number of chocolates that divides the number of chocolates with both the students. Now, I don't know how do I pair them! Not everyone can be paired with everyone, friendship issues. Can you help me out?"

You are given the number of chocolates with each student and all the possible pairs of the form (i,j) where ith and jth student can be paired. Help Bruce pair the students, so as to maximize the number of chocolates he can have .

You may assume:

• No pairs should overlap. No student is left alone (except Bruce).
• Total number of students in class is always odd.
• No one is absent on the Chocolate Day!
• For a possible pairing (i,j) , ( i+j )mod 2 >0

HackerEarth Bruce and the Chocolates problem solution.

#include<bits/stdc++.h>
 
 
using namespace std;
 
#define gc getchar_unlocked
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define N 205 //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 gcd(int u, int v) {
return (v != 0)?gcd(v, u%v):u;
}
int inp[205]={0};

int main () 
{
//freopen("temp","r",stdin);
//freopen("out1","w",stdout);
 int t,m,i,j,si;
cin >> t;
while (t--)
{
  cin >>si>>m;
         assert(si%2==1);
  si--;
  n=si/2;
  for( i=0;i<si;i++)
    cin>>inp[i];
 for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        cost[i][j]=0;
  while(m--)
  {
     int ta,tb;
     cin>>ta>>tb;
           assert(ta>=1 && ta<=si);
           assert(tb>=1 && tb<=si);
           //assert(tb>=1);
           //assert(ta<=n);
           //assert(tb<=n);
           assert(  (ta+tb)%2==1);
     ta--;
     tb--;
     if(ta%2==1)
     swap(ta,tb);
     cost[ta/2][tb/2]= gcd(inp[ta],inp[tb]);
  }

  ll int  ans = hungarian();
  cout << ans << "\n";
}
return 0;
}

Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define sz size()

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;
const int INF = 1000000000;
int A[222];

int n,m;
int a[222][222];
int edge[222][222];

void hungarian() {
  vector < int > u ( n + 1 ) , v ( m + 1 ) , p ( m + 1 ) , way ( m + 1 ) ;
  for ( int i = 1 ; i <= n ; ++i ) {
    p[0] = i ;
    int j0 = 0 ;
    vector < int > minv ( m + 1 , INF ) ;
    vector < char > used ( m + 1 , false ) ;
    do {
      used [ j0 ] = true ;
      int i0 = p [ j0 ] ,  delta = INF,  j1 ;
      for ( int j = 1 ; j <= m ; ++ j )
        if ( ! used [ j ] ) {
          int cur = a [ i0 ] [ j ] - u [ i0 ] - v [ j ] ;
          if ( cur < minv [ j ] )
            minv [ j ] = cur,  way [ j ] = j0 ;
          if ( minv [ j ] < delta )
            delta = minv [ j ] ,  j1 = j ;
        }
      for ( int j = 0 ; j <= m ; ++j )
        if ( used [ j ] )
          u [ p [ j ] ] += delta,  v [ j ] -= delta ;
        else
          minv [ j ] -= delta ;
      j0 = j1 ;
    } while ( p [ j0 ] != 0 ) ;
    do {
      int j1 = way [ j0 ] ;
      p [ j0 ] = p [ j1 ] ;
      j0 = j1 ;
    } while ( j0 ) ;
  }

  vector < int > ans ( n + 1 ) ;
  for ( int j = 1 ; j <= m ; ++ j )
    ans [ p [ j ] ] = j ;
  int res = 0;
  rep(i,1,n+1) {
    if(edge[i][ans[i]]) {
      res += __gcd(A[2*i-1], A[2*ans[i]]);
    }
  }
  P(res);
}


int main() {
  int t;
  S(t);

  while(t--) {

    int e;
    S2(n,e);

    rep(i,1,n) S(A[i]);

    n = n/2;
    m = n;

    memset(a, 0, sizeof(a));
    memset(edge, 0, sizeof(edge));
    while(e--) {
      int x,y;
      S2(x,y);
      if(y&1) swap(x,y);
      a[(x+1)/2][y/2] = -1 * __gcd(A[x], A[y]);
      edge[(x+1)/2][y/2] = 1;
    }
    hungarian();
  }

  return 0;
}