## Sunday, December 28, 2014

### 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 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){
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();
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;
}
}
for(int i=0;i<N;++i){
for(int j=0;j<N;++j){
}
}
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)

- 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)
*/