TopCoder SRM 371 Div. 1 Medium - ChessMatchup

Problem Statement:
TopCoder SRM 371 Div. 1 Medium - ChessMatchup

Solution:
Just learnt Kuhn-Munkres algorithm, and tried a related problem. The problem is a straight forward modification of maximum weight perfect matching. Here is an implementation:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;

int INF = (int) 1e9;

class ChessMatchup {
public:
    int adj[102][102];
    int M, N;
    int l[102], S[102], T[102], Nq[102];
    int path[102], match[102];
    int root;
    int par[102];

    void computeNq(){
        memset(Nq, 0, sizeof Nq);
        for(int i=0;i<N;++i){
            if(!S[i])continue;
            for(int j=N;j<2*N;++j){
                if(l[i] + l[j] == adj[i][j]){
                    Nq[j] = 1;
                    if(match[j] != i) par[j] = i;
                }
            }
        }
    }

    bool TequalsNq(){
        for(int i=N;i<2*N;++i){
            if(T[i] != Nq[i]) return false;
        }
        return true;
    }

    void augment_path(int v, int state){
        int u = path[v];
        if(u == v) return;
        if(state){
            match[u] = v;
            match[v] = u;
        }
        augment_path(u, state^1);
    }

    int maximumScore(vector<int> us, vector<int> them){
        N = us.size();
        for(int i=0;i<N;++i) memset(adj[i], 0, sizeof adj[i]);
        memset(l, 0, sizeof l);
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                int tmp = us[i] - them[j];
                if(tmp > 0) tmp = 2;
                else if(tmp == 0) tmp = 1;
                else tmp = 0;
                adj[i][j+N] = tmp;
                adj[j+N][i] = tmp;
            }
        }
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                l[i] = max(l[i], adj[i][j+N]);
            }
        }
        M = 0;
        for(int i=0;i<2*N;++i) match[i] = i;
        while(M != N){
            memset(S, 0, sizeof S);
            memset(T, 0, sizeof T);
            for(int i=0;i<2*N;++i) path[i] = i;
            for(int i=0;i<N;++i){
                if(match[i] == i){
                    S[i] = 1;
                    root = i;
                    break;
                }
            }
            while(true){
                computeNq();
                if(TequalsNq()){
                    int alpha = 12345;
                    for(int i=0;i<N;++i){
                        if(!S[i])continue;
                        for(int j=N;j<2*N;++j){
                            if(T[j])continue;
                            alpha = min(alpha, l[i] + l[j] - adj[i][j]);
                        }
                    }
                    assert(alpha != INF && alpha != 0);
                    for(int i=0;i<2*N;++i){
                        if(S[i]) l[i] -= alpha;
                        if(T[i]) l[i] += alpha;
                    }
                    computeNq();
                }
                int y = -1;
                for(int i=N;i<2*N;++i){
                    if(Nq[i] && !T[i]) {
                        y = i;
                        break;
                    }
                }
                assert(y >= 0);
                if(match[y] == y){
                    path[y] = par[y];
                    augment_path(y, 1);
                    ++M;
                    break;
                } else {
                    path[y] = par[y];
                    path[match[y]] = y;
                    S[match[y]] = 1;
                    T[y] = 1;
                }
            }
        }
        int ans = 0;
        for(int i=0;i<2*N;++i){
            ans += l[i];
        }
        return ans;
    }
};

Below is a short description of Hungarian method for finding maximum weight matching that I summarised last night :P

/*
KUHN-MUNKRES ALGORITHM for MAXIMUM WEIGHT MATCHING.
Given a bipartite graph, find the maximum weigth matching, i.e. the
total sum of the weights of the matching is maximum.

Representation of the bipartite graph:
Let G = (V,E) be the graph, then there exist X \subset V and Y \subset V, such that
1.  X \union Y = G
2.  X \intersect Y = \empty
3.  E \in (X \cross_product Y)

For x \in X and y \in Y, (x,y) \in E, let w(x,y) be the weight of that edge.

Terminologies:
1.  _Perfect matching_ is a matching M \in E such that each vertex \in V 
    is incident to one and only one edge \in M.
2.  _Labelling_ l : V -> R is a function that labels vertices to real numbers.
3.  A _feasible labelling_ is a labelling such that if x \in X and y \in Y, then
    l(x) + l(y) >= w(x,y)
4.  The _equality graph_ of G has all the edges Eq in E with property
    l(x) + l(y) == w(x,y) for all (x,y) \in Eq
5.  Let N(u) be the neighbors v of u, such that w(us,v) == l(u) + l(v).
    Furthermore, if S is a set of vertices, then N(S) = \union_{u \in S} N(u)
6.  _Alternating path_ is a path that passes through edges \in M and E-M alternatingly.
    Alternating path is said to be _augmenting_ if two end points of the path
    are free vertices. 
7.  Augmenting path always has one more edge in E-M than M. Hence flipping them
    will result in bigger matching M'.
8.  An alternating tree is a tree with a free vertex as the root, and all path from the root form
    alternating paths.

Kurn-Munkres Theorem:
For a feasible labelling l, if M is a perfect matching in Eq, then M is
a maximum weight matching in G.

Proof:
Suppose M is a perfect matching in G, may not be in Eq.
Then we have:
\sum_{e \in M} w(e) <= \sum_{e = (x,y) \in M} l(x) + l(y)
                    == \sum_{v \in V} l(v)
So sum of l(v) is the upper bound to the weight of the matching. Therefore,
if we have Mq be the perfect matching in Eq, then we have
\sum_{e \in Mq} w(e) == \sum_{v \in V} l(v)
which is optimal maximum weigth matching. #shown

Hungarian Method:
1. Initialize a labelling l, and a matching M in Eq.
2. Let S be a set of vertices in X, and T be a set of vertices in Y.
   Initially S and T are both empty.
3. While M is not perfect matching:
    Choose a free vertex f \in X such that S contains f, and T is empty.
    i.e. S = {f}, T = {}
    4. If N(S) == T:
        Improve labelling l to l' (therefore Eq to Eq'), by:
        Find alpha = \min_{x \in S, y \not \in T} l(x) + l(y) - w(x,y)
        then for all v \in V:
            if v \in S: l(v) = l(v) - alpha
            if v \in T: l(v) = l(v) + alpha
            otherwise, do nothing to l(v)

        This updates ascertain that:
            - if u \in S and v \in T, then if (u,v) \in Eq then (u,v) \in Eq'
            - if u \not \in S and v \not \in T, then if (u,v) \in Eq then (u,v) \in Eq'
            - for u \in S and v \not \in T, there will be some (u,v) \in Eq'
        Also ensuring the correctness of alternating tree built later on.
    5. If N(S) != T:
        Consider a vertex y \in N(S) - T.
        If y is a free vertex, then we have an augmenting path from f to y:
            Augment M and go to 3.
        Otherwise, y is matched to a vertex x:
            Extend T = T \union y and S = S \union x, and go to 4.

Running time complexity: O(V^3)
*/