TopCoder SRM 447 Div 1 Medium (PeopleYouMayKnow)

Problem link : http://www.topcoder.com/stat?c=problem_statement&pm=10580

This is a nice problem because it can be solved in different ways - dynamic programming, maximum flow or bipartite matching.

The solution of the problem in one line would be

calculate maximum number of node disjoint paths from node p1 to p2 whose length is less than or equal to 3.

Finding maximum number of node disjoint paths in a graph is a Maximum Flow problem. And to check if the length of the path is within range or not, we have to assign unit costs to each edge and use Bellman Ford algorithm when finding augmenting path. Also, note that for finding node disjoint paths, you have to split each node in 2 to incorporate node capacity constraint. For more info, check the Wikipedia page.

This was the general solution. But as the length of the path is at most 3, we can improvise on it. There can be 2 types of cases -

1. The length of the path is 2 i.e. there is just one node between p1 and p2. In this case, we have to remove the node.
2. The length of the path is 3 and none of the intermediate node satisfies the previous case. In this case, we need to remove at least one of the nodes.

Case 1 can be solved easily - by just checking the adjacency matrix. To solve the Case 2s, we need to create a bipartite graph with nodes connected with p1 on one side and nodes connected with p2 on the other and find maximum matching in it. As the number of nodes is at most 40, one of the bipartite set will contain less than 20 nodes. So, we can just implement a bitmask dp here. Find more information about this approach on the official match editorial.

Bipartite matching is easier to code amongst all the approaches. Check my source code below. Note the case one the input graph is disconnected.

/*
Problem Name : PeopleYouMayKnow
Problem Number : TopCoder SRM 447 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10580
Problem Type : Dynamic Programming, Bipartite Matching
Difficulty : 6.5 / 10
Interest : 7.5 / 10
Complexity : O(N^3)
Date : November 26, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 40

bool a1[MAXN+2][MAXN+2], a2[MAXN+2][MAXN+2];
bool graph[MAXN+2][MAXN+2];
bool visited[MAXN+2];
bool flag[MAXN+2];
int matchL[MAXN+2];
int matchR[MAXN+2];

struct PeopleYouMayKnow{
 int n;
 bool bpm(int u) {
  int i;
  rep(i,n) if(graph[u][i] && visited[i] == false) {
   visited[i] = true;
   if(matchR[i] < 0 || bpm(matchR[i])) {
    matchL[u] = i;
    matchR[i] = u;
    return true;
   }
  }
  return false;
 }

 int maximalScore(vector <string> friends, int p1, int p2) {
  int i,j,k;
  n = friends.size();
  rep(i,n) rep(j,n) a1[i][j] = a2[i][j] = (friends[i][j] == 'Y');
  rep(k,n) rep(i,n) rep(j,n) a2[i][j] |= (a2[i][k] & a2[k][j]); //floyd warshall
  if(!a2[p1][p2]) return 0; //not connected

  int res = 0;
  memset(graph,0,sizeof(graph));
  memset(flag,0,sizeof(flag));
  flag[p1] = flag[p2] = 1;
  rep(i,n) if(a1[p1][i] && a1[i][p2]) { flag[i] = 1; res++; } //connected by 1 intermediate friend
  //build graph
  rep(i,n) if(!flag[i]) {
   rep(j,n) if(!flag[j]) {
    if(a1[p1][i] && a1[i][j] && a1[j][p2]) {
     graph[i][j] = 1;
    }
   }
  }

  //bpm
  memset(matchL,-1,sizeof(matchL));
  memset(matchR,-1,sizeof(matchR));
  rep(i,n) if(!flag[i]) {
   memset(visited,0,sizeof(visited));
   if(bpm(i)) res++;
  }
  return res;
 }
};