Friday, August 28, 2009

TC SRM447 D1 500 (PeopleYouMayKnow)

The problem statement can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=10580

The problem itself is pretty simple: it asks us to given a friends graph determine the number of friends to remove such that there are no paths from friend A to friend B which has a length less than 3.

The key observation is to remove all friends which have a shortest path between A and B which exceeds 3 as these will never conflict with our objective. To determine intermediate distances we can just use Floyd-Warshall's algorithm to calculate all-pairs shortest paths between friends. Then we can discard any nodes which violate dist[person1][i] + dist[i][person2] <= 3. Note that the problem fixes the constraint to not allow any paths with a length of less than 3 - this allows us to use a simple bipartite matching to determine the minimum cut of the network. For the general problem of having a length less than n, we can simply use a network flow algorithm (which we use for the implementation here).

We can divide the friends into two (one used as an in-node, the other used as an out-node) and run the maximum flow algorithm over the network. This concept is very similar to the one used in TC SRM360 D1 500 (Prince of Persia).

Implementation below:


class PeopleYouMayKnow {
public:
int maximalScore(vector <string>, int, int);
};

int augment(int cur, int flow, int ret);

int adjmat[201][201];
int used[201][201];
bool visited[201];
int t;

int maxflow() {
int flow = 0, thisFlow = 0;
memset(visited,false,sizeof(visited));
while ((thisFlow = augment(0, INT_MAX-1, 0)) != 0) {
memset(visited,false,sizeof(visited));
flow += thisFlow;
}
return flow;
}

int augment(int cur, int flow, int ret) {
if (cur == t-1) return flow;
visited[cur] = true;
for (int i = 0; i < t && ret == 0; i++) {
if (adjmat[cur][i] > used[cur][i] && !visited[i] &&
(ret = augment(i, min(flow,adjmat[cur][i]-used[cur][i]), 0)) > 0)
used[cur][i] += ret;
else if (used[i][cur] > 0 && !visited[i] &&
(ret = augment(i,min(flow, used[i][cur]), 0)) > 0)
used[i][cur] -= ret;
}
return ret;
}

int distTable[51][51];
int validNodes[51];
#define INF (1<<20)

int PeopleYouMayKnow::maximalScore(vector <string> friends, int A, int B) {
int res = 0;
int sz = friends.size();
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
if (i == j) distTable[i][j] = 0;
else distTable[i][j] = friends[i][j] == 'Y' ? 1 : INF;
for (int k = 0; k < sz; k++)
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
distTable[i][j] <?= distTable[i][k] + distTable[k][j];
// build the network - allowing infinite capacities between
// out -> in nodes and restricting capacities between nodes with 1 capacity
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
if (friends[i][j] == 'Y')
adjmat[i+1+sz][j+1] = INF;
for (int i = 0; i < sz; i++)
if (distTable[person1][i] + distTable[i][person2] > 3)
for (int j = 0; j < sz; j++) adjmat[j+1][i+1] = adjmat[i+1][j+1] = 0;
else
validNodes[i] = 1;
for (int i = 0; i < sz; i++)
if (validNodes[i]) adjmat[i+1][i+1+sz] = 1; else adjmat[i+1][i+1+sz] = 0;
adjmat[0][person1+1] = INF;
adjmat[person1+1][person1+1+sz] = INF;
adjmat[person2+1][person2+1+sz] = INF;
adjmat[person2+1+sz][2*sz+1] = INF;
t = 2*sz+2;
return res = maxflow();
}

No comments:

Post a Comment