TopCoder SRM 480 Div 1 Medium (NetworkSecurity)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10736

This is a nice graph theory problem. The key observation here is that there is no point placing a data gate on an edge that is not directly connected to a server. Because in this way it can serve maximum number of clients. You might think if a client is connected to all the servers through some path and all the paths share an edge (a bridge) that is not directly connected to a server, why not just place a data gate on that edge as it will be useful for all of the paths? The answer is though it comes handy for the client in question, it does not do any help for the clients that are directly connected to the server. They still need a data gate between them and server. So, we have to place data gates further down the path anyway and that gate on the bridge edge will just be redundant.



However, not all the clients that are directly connected to a server will require a data gate because sometimes it can choose an alternative path that goes through other clients. So, we have to place gates only for those clients for which we can't find any alternative path.

Check the source code for more explanations -

/*
Problem Name : NetworkSecurity
Problem Number : TopCoder SRM 480 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10736
Problem Type : Graph Theory
Difficulty : 5 / 10
Interest : 7 / 10
Complexity : O((N+M)^3)
Date : November 24, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

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

struct NetworkSecurity{
 bool a[MAXN+2][MAXN+2]; //adjacency matrix
 int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
  int i,j,k,res;
  int n = clientCable.size(),m = serverCable[0].size();
  memset(a,0,sizeof(a));
  rep(i,n) rep(j,n) if(clientCable[i][j] == 'Y') a[i][j] = 1;
  rep(i,n) rep(j,m) if(serverCable[i][j] == 'Y') a[i][j+n] = 1;
  rep(k,n) rep(i,n) rep(j,n) a[i][j] |= (a[i][k]&a[k][j]);//floyd warshall
  res=n*m;
  rep(i,n) rep(j,m) {
   if(a[i][j+n] == 0) res--; //if no path to server, then no need to place a data gate
   else { //if we can find an intermediate node betwen the current node and server, we can use the gate for that node
    rep(k,n) if(k!=i && a[i][k] && a[k][j+n]) { res--; break;}
   }
  }
  return res;
 }
};