HackerEarth Beating the dices in their own game problem solution

In this HackerEarth Beating the dices in their own game problem solution A Dice is a really great invention made in the history of the mankind. They try to capture the notion of randomness and one can experience how good they are, by trying to throw a dice such that it lands on a particular integer value written on one of its face. There are many games that revolve around the use of dices and this property of randomness of theirs. Casinos use them heavily to attract customers who try their luck in the hope of winning against the randomness.

However, by the use of modern technology, the star gambler HackerEarthly has made a breakthrough in trying to beat the dices. He has developed a device which can throw a particular face for a dice. But, like most of the devices in the modern world, it needs energy and sometime takes different amount of energy to throw different faces on the same dice.

The Jindal Casino has smelled something fishy by the winning streak of HackerEarthly and has introduced a new tournament to try to stop HackerEarthly. In the tournament, the player will be given N dices given and on each dice, there are Mi faces, with a value written on each of it such that no two faces have the same value. They have done so in the hope of increasing the randomness of a game. They believe that more the number of dices, the more randomness would be there. Now, the tournament consists of Q games, and each game, you will be given a set of N values (K1, .... KN) . The participants win a game if they can throw these exact N values from the N dices given to them. (Note that it is not required that the first value in the game has to be thrown from the first dice, it can be from any, but the value on the top face of each dice will be counted only once.) Note that it is possible that Jindal Casino is cheating and there is no way you can win a game.

Now, HackerEarthly was given the N dices in the beginning with which he will be playing the tournament. He has already computed how much energy he has to use to throw a particular face on a given dice. And he has computed this for all faces for each of the dice given. Since there are multiple games to be played, he is inclined to use minimum energy to win each game. The energy used in a game would be the sum of energies that HackerEarthly requires to throw a particular face on each of his dice. Help him compute the minimum energy value would be required to win each

HackerEarth Beating the dices in their own game problem solution.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <math.h>
#include <cassert>
#include <string.h>
#include <stack>

using namespace std;

#define DEBUG if(0)
#define pb push_back
#define mp make_pair

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;

const double PT = acos(-1.0);
const double EPS = 1e-11;

const LL INF=20000000000000LL;
#define MAXN 220

vector<pair<LL, LL> > inp[MAXN];
LL setB[MAXN];
LL g[MAXN][MAXN], linky[MAXN];
LL lx[MAXN], ly[MAXN], slack[MAXN];
LL visy[MAXN], visx[MAXN], flag=0, N;

bool check(int now){
    visx[now]=flag;

    for(int i=0;i<N;i++){
        if(lx[now]+ly[i]==g[now][i] && visy[i]!=flag){
            visy[i]=flag;

            if(linky[i]==-1 || check(linky[i])){
                linky[i]=now;
                return true;
            }
        }
        slack[i]=min(slack[i], g[now][i]-lx[now]-ly[i]);
    }
    return false;
}

LL hungarian(int n){
    N=n;
    for(int i=0;i<n;i++) 
        lx[i]=INF, ly[i]=0, linky[i]=-1;
    for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++)
            lx[i] = min(lx[i], g[i][j]);

    for(int vec=0; vec<n; vec++){
        for(int j=0; j<n; j++) 
            slack[j] = INF;

        for(flag++; !check(vec); flag++){
            LL dt = INF;

            for(int j=0; j<n; j++) 
                if(visy[j]!=flag)
                    dt = min(slack[j], dt);

            for(int i=0;i<=vec;i++) 
                if(visx[i]==flag) 
                    lx[i]+=dt;

            for(int j=0;j<n;j++) 
                if(visy[j]==flag)
                    ly[j]-=dt;

            for(int j=0;j<n;j++) 
                slack[j]=INF;

            if(lx[vec]>=INF) 
                return INF + 1;
        }
    }
    LL ans=0;

    for(int i=0;i<n;i++) 
        ans+=lx[i]+ly[i];
    return ans;
}

int main()
{
    int q, n, m;
    long long u,v,c;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
      scanf("%d", &m);
      for(int j=0;j<m;j++){
        scanf("%lld %lld", &u, &c);
        inp[i].push_back(make_pair(u,c));
      }
      //sort(inp[i].begin(), inp[i].begin()+m);
    }
    scanf("%d", &q);
    while(q--){
        //scanf("%d%d",&n, &m);
        for(int i=0;i<n;i++){
          scanf("%lld", &setB[i]);
        }
        for(int i=0;i<n;i++) 
            for(int j=0;j<n;j++) 
                g[i][j]=INF;

        /*for(int i=0;i<m;i++){
            scanf("%d %d %d",&u,&v,&c);
            g[u-1][v-1]=c;
        }*/
        //sort(setB, setB+n);
        for(int i=0;i<n;i++){
          for(int j=0;j<inp[i].size();j++)
            for(int k=0;k<n;k++)
              if(inp[i][j].first==setB[k])
                g[i][k]=inp[i][j].second;
        }

        LL res=hungarian(n);

        if(res>=INF) //meaning some vertex is unmatched, hence not complete matching
            printf("-1\n");
        else 
            printf("%lld\n", res);
    }
    return 0;
}

Second solution

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
 
struct MinimumCostMaximumFlow {
  typedef int Index; typedef int Flow; typedef int Cost;
  static const Flow InfCapacity = INF; static const Cost InfCost = INF;
  struct Edge {
    Index to; Index rev;
    Flow capacity; Cost cost;
  };
  vector<vector<Edge> > g;
  void init(Index n) { g.assign(n, vector<Edge>()); }
  void add(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
    Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0; e.cost = cost, f.cost = -cost;
    g[i].push_back(e); g[j].push_back(f);
    g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
  }
  void addB(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
    add(i, j, capacity, cost);
    add(j, i, capacity, cost);
  }
  pair<Cost,Flow> minimumCostMaximumFlow(Index s, Index t, Flow f = InfCapacity, bool useSPFA = false) {
    int n = g.size();
    vector<Cost> dist(n); vector<Index> prev(n); vector<Index> prevEdge(n);
    pair<Cost,Flow> total = make_pair(0, 0);
    vector<Cost> potential(n);
    while(f > 0) {
      fill(dist.begin(), dist.end(), InfCost);
      if(useSPFA || total.second == 0) {
        deque<Index> q;
        q.push_back(s); dist[s] = 0; vector<bool> inqueue(n);
        while(!q.empty()) {
          Index i = q.front(); q.pop_front(); inqueue[i] = false;
          for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
            const Edge &e = g[i][ei]; Index j = e.to; Cost d = dist[i] + e.cost;
            if(e.capacity > 0 && d < dist[j]) {
              if(!inqueue[j]) {
                inqueue[j] = true;
                q.push_back(j);
              }
              dist[j] = d; prev[j] = i; prevEdge[j] = ei;
            }
          }
        }
      }else {
        vector<bool> vis(n);
        priority_queue<pair<Cost,Index> > q;
        q.push(make_pair(-0, s)); dist[s] = 0;
        while(!q.empty()) {
          Index i = q.top().second; q.pop();
          if(vis[i]) continue;
          vis[i] = true;
          for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
            const Edge &e = g[i][ei];
            if(e.capacity <= 0) continue;
            Index j = e.to; Cost d = dist[i] + e.cost + potential[i] - potential[j];
            if(dist[j] > d) {
              dist[j] = d; prev[j] = i; prevEdge[j] = ei;
              q.push(make_pair(-d, j));
            }
          }
        }
      }
      if(dist[t] == InfCost) break;
      if(!useSPFA) for(Index i = 0; i < n; i ++) potential[i] += dist[i];
      
      Flow d = f; Cost distt = 0;
      for(Index v = t; v != s; ) {
        Index u = prev[v]; const Edge &e = g[u][prevEdge[v]];
        d = min(d, e.capacity); distt += e.cost; v = u;
      }
      f -= d; total.first += d * distt; total.second += d;
      for(Index v = t; v != s; v = prev[v]) {
        Edge &e = g[prev[v]][prevEdge[v]];
        e.capacity -= d; g[e.to][e.rev].capacity += d;
      }
    }
    return total;
  }
};
 
 
int main() {
  int N;
  scanf("%d", &N);
  assert(1 <= N && N <= 100);
  vector<map<int,int> > costs(N);
  rep(i, N) {
    int M;
    scanf("%d", &M);
    assert(1 <= M && M <= 100);
    rep(j, M) {
      int u, c;
      scanf("%d%d", &u, &c);
      assert(1 <= u && u <= 1000000000);
      assert(1 <= c && c <= 1000000);
      assert(!costs[i].count(u));
      costs[i][u] = c;
    }
  }
  int Q;
  scanf("%d", &Q);
  assert(1 <= Q && Q <= 10);
  rep(ii, Q) {
    MinimumCostMaximumFlow mcf;
    int src = N + N, dst = src + 1;
    mcf.init(dst + 1);
    rep(i, N)
      mcf.add(src, i, 1);
    rep(j, N)
      mcf.add(N + j, dst, 1);
    rep(i, N) {
      int a;
      scanf("%d", &a);
      assert(1 <= a && a <= 1000000000);
      rep(j, N) if(costs[j].count(a))
        mcf.add(i, N + j, 1, costs[j][a]);
    }
    pair<int,int> res = mcf.minimumCostMaximumFlow(src, dst);
    if(res.second != N)
      puts("-1");
    else
      printf("%d\n", res.first);
  }
  return 0;
}