Z-Training :: Slicice

Problem Link: http://www.z-training.net/tasks.php?show_task=5000000529

Shortly the problem is,
There are N players (child). (1<=N<=100). They had some races. In each race, exactly 2 people participated. The winner received 2 points (cards, in the problem), looser receives 0 point. In case of a draw, both receives 1 point. After many races has taken place, you are given the points (cards) of each of the players, and a partial list of races where the id of the players are known, but the results are unknown. Note that, the list is partial (i.e. more races might have took place but they forgot who raced against whom). You have to construct a complete list of races with results.

The Solution:
This can be solved with max flow (experience will tell you that). Observe that, the total number of purchases (races) that took place is, total _number_of_cards / 2. Because, every purchase produces exactly 2 points, and distributes them according to the result.

So, we can build a flow network that has a vertex for each child and each purchase (known + unknown). The child-vertices are connected to the source with an edge with capacity equal to the number of cards of that child. For each known race (a,b), child a and child b are connected to that race-vertex with edge capacity 2. Every child is connected to every vertex that represents an unknown race with edge capacity 2. Vertices representing races will be connected to the sink with edge capacity 2.

Now, we shall be able to build a possible solution (any valid solution is allowed) from the maximum flow in this network.

Let, (a,b) is a known race and x is the vertex representing this race. Now, the pair (flow[a][x], flow[b][x]) will correspond to the result of this race. A (2,0) would mean, 'a' had own, (0,2) means, 'b' had own, and (1,1) would correspond to a draw.

Now let, x represent an unknown race. The edge (x,sink) has capacity 2. It is ensured in the problem that, the solution will always exist. So, the total incoming flow for x will be exactly 2. In fact it will be true for every race-vertex. So, there will be either a single incoming edge with flow 2, or two incoming edges with flow 1 for each. In the second case, the corresponding child-vertices will correspond to the participants of a race that has been drawn. In the first case, the child that produces that flow amount 2, will be the winner of that race. The looser is unknown. But, because any solution is allowed, we can assign any other child as the looser.

I have used Edmonds-Karp Algorithm to solve this problem (because, that's the only max-flow implementation that I know)

Complexity:
Maximum Total Nodes, V = 100 + 1000 + 2 = 1102 ( total child + total races + source and sink )
Maximum Total Edges, E = 100 + 100*1000 + 1000 = 101100 ( source to child + child to race + race to sink )
Edmonds-Karp has a complexity of O(VE²)
That gives us 1102*101100*101100 = 11263773420000, which is too large to run in 5 seconds!
But wait! The max-flow for this network will never exceed 1000 and at each step of Edmonds-Karp, the total flow increases by at least 1. So, the total number of augmentation won't exceed 1000. To find an augmenting path, Edmonds-Karp uses BFS that has complexity O(V+E) . So, in the worst case, Edmonds Karp will need at most 1000*(1102+101100) = 102202000 operations which clearly, would run in way under 5 seconds!

Here's the code:

#include<stdio.h>
#include<string.h>

#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))

#define MAX_NODE 1+100+1000+1+5
#define INF (1<<29)

int src, sink;
int child, recall, card[105], total_card;

struct edge
{
    int u, v, cap, flow;
    
    edge(){}
    edge(int _u, int _v, int _cap, int _flow) 
    { 
        u = _u; v = _v; cap = _cap; flow = _flow; 
    }  
};

vector<edge> E;
vector<int> adj[MAX_NODE];

int rec_u[1005], rec_v[1005];

void add_edge(int u, int v, int cap)
{
    adj[u].push_back(E.size());
    E.push_back(edge(u,v,cap,0));
    
    adj[v].push_back(E.size());
    E.push_back(edge(v,u,0,0));
}

void build_network()
{
    int total_purchase = total_card / 2;
    
    src = 0;
    sink = child + total_purchase + 1;
    
    // initialize
    E.clear();
    
    // src to child
    REP(u,1,child)
    add_edge(src,u,card[u]);
    
    // child to recalled-purchase, and recalled-purchases to sink
    // recalled-purchases are represented by nodes (child+1+i)
    FOR(i,recall)
    {
        add_edge(rec_u[i],child+1+i,2);
        add_edge(rec_v[i],child+1+i,2);
    
        add_edge(child+1+i,sink,2);
    }
    
    // child to unknown-purchases
    // unknown-purchases are represented by nodes (child+1+i)
    REP(u,1,child)
    for(int i = recall; i < total_purchase; ++i)
    {
        add_edge(u,(child+1+i),2);
    }
    
    // unknown-purchases to sink
    for(int i = recall; i < total_purchase; ++i)
    {
        add_edge((child+1+i),sink,2);   
    }
}

int botnek[MAX_NODE], parent[MAX_NODE];

void max_flow()
{
    while(true)
    {
        REP(i,0,sink) 
        parent[i] = -1;
        
        queue<int> Q;
        Q.push(src);
        
        botnek[src] = INF;
        parent[src] = -2;
        
        bool found = false;
        
        while(!Q.empty() && !found)
        {
            int u = Q.front();
            
            Q.pop();
            
            FOR(i,adj[u].size())
            {
                int k = adj[u][i]; // edge-k goes out from node u
                int v = E[k].v; // v is the next node
                
                if(parent[v] != -1) continue; // already seen
                                              
                int res_cap = E[k].cap-E[k].flow;
                
                if(res_cap > 0)
                {
                    parent[v] = k;
                    botnek[v] = min(res_cap,botnek[u]);
                    
                    if(v == sink)
                    {
                        found = true;
                        break;
                    }   
                    else
                    {
                        Q.push(v);
                    }                
                }
            }
        } 
        
        if(!found) break;
        
        int v = sink;
        
        while(v != src)
        {
            int k = parent[v];
            
            E[k].flow += botnek[sink];
            E[k^1].flow -= botnek[sink];
            
            v = E[k].u;
        }
    }
}

int F[1105][1105];

void output()
{
    int total_purchase = total_card / 2;
    printf("%d\n",total_purchase);
    
    REP(i,0,sink)
    {
        FOR(j,adj[i].size())
        {
            int to = E[adj[i][j]].v;
            F[i][to] = E[adj[i][j]].flow;   
        }
    }
        
    FOR(i,recall)
    {
        printf("%d %d %d\n",rec_u[i],rec_v[i],F[rec_u[i]][child+1+i]);   
    }
    
    for(int i = recall; i < total_purchase; ++i)
    {
        vector<int> temp;
        
        REP(c,1,child) if(F[c][child+1+i])
        temp.push_back(c);
        
        if(temp.size() == 2)
        printf("%d %d 1\n",temp[0],temp[1]);
        else
        printf("%d %d 2\n",temp[0],(temp[0]==1?2:1));   
    }
}

int main()
{    
    
    scanf("%d%d",&child,&recall);
    
    total_card = 0;
    
    REP(i,1,child)
    {
        scanf("%d",card+i);
        total_card += card[i];
    }
    
    FOR(i,recall)
    {
        scanf("%d%d",rec_u+i,rec_v+i);
    }
    
    build_network();
    max_flow();
    output();
        
    return 0;
}

this blog is inspired by: http://one-problem-a-day.blogspot.com