TC SRM 459 D2-1000 (ParkAmusement)

Category: Dynamic Programming, Graph Theory
URL: http://www.topcoder.com/stat?c=problem_statement&pm=10723

The problem describes having N landings in the amusement park. The landings can be terminating (i.e. the ride ends at this landing) which are either proper exits or crocodile ponds. The landings can also be non-terminating which means that you will slide down further or until you are stalled with no valid adjacent landings. All of the N landings have different heights and we can only slide down from a taller landing to a shorter one (by the laws of gravity). We start at a random landing and we wish to calculate the probability that we started at a specific landing given that we only went through exactly K different pipes to get safely home (i.e. at a proper exit and not at either a crocodile pond or a dead-end landing).

This problem is best split into two parts. The first is to calculate the probability we reach home from a specific starting point. The second is to calculate the probability that out of all the viable starting points we chose the specific starting landing. We are already given the adjacency matrix in terms of a vector/array of strings which we proceed to convert into a more usable format. We first keep track of exits - i.e. whether or not they are proper exits (home) or crocodile ponds. This is done by specifically checking whether or not landings[i][i] is '0' or not (based on the problem definition). If it's not '0', then the current vertex is an exit and we proceed to determine which type. Otherwise, we add the edges into our adjacency list. This is shown below:

vector<vector<int> > adjlist;   // adjacency list
int table[51];   // the exit table for each vertex, 0 if it's not an exit, 1 if it's home exit, 2 if it's a pond exit

...
double ParkAmusement::getProbability(vector <string> landings, int startLanding, 
      int K) {
   adjlist = vector<vector<int> >(landings.size(), vector<int>());
   for (int i = 0; i < landings.size(); i++) {
      if (landings[i][i] != '0') {
         // exit
         if (landings[i][i] == 'P') table[i] = 2;   // pond
         else table[i] = 1; // exit
         continue;
      }
      for (int j = 0; j < landings[i].size(); j++) {
         if (landings[i][j] == '1') adjlist[i].push_back(j);
      }
   }
...

Once we have parsed the input into a better format, we need to find out the probability of reaching home from a fixed starting vertex/landing. We can accomplish this through a DFS-like recursive function by keeping track of how many steps we have left to reach home. This involves keeping track of which vertex/landing we are currently at and how many hops left we must use. The base case is when the number of steps left is zero, if we are at an exit and it's the proper one (i.e. an 'E' in the matrix) then we have reached home - otherwise we have failed in our mission.

We utilise basic probability calculations to compute our chances of succeeding. If we arrive at a landing that has M out-going edges, then the probability of choosing a particular edge is 1/M. Therefore, the probability we will survive is simply the sum of 1/M * f(edge i, K-1) for all out-going edges i. The base cases are obvious, probability of surviving is 1.0 if we reach an 'E' exit otherwise it's 0.0. The function below illustrates this concept:

double calcPr(int startNode, int K) {
   if (K == 0) {
      // check if it's the exit
      if (table[startNode] != 1) return 0.0;
      return 1.0;
   }
   double res = 0.0;
   // note: if there are no more valid out-going edges it defaults to a 
   //    0.0 probability
   int poss = adjlist[startNode].size();
   for (int i = 0; i < adjlist[startNode].size(); i++) {
      res += (1.0 / poss) * calcPr(adjlist[startNode][i], K-1);
   }
   return res;
}

However, we can optimise this by memoising it. Otherwise we may run into trouble with time limits for the larger cases. This is easily done by setting up a cache table and marking it with a sentinel value to determine whether the state has been computed or not. Since no probability can be negative, we can exploit this fact.

double dp[51][51];

double calcPr(int startNode, int K) {
   if (dp[startNode][K] >= 0.0) return dp[startNode][K];
   if (K == 0) {
      if (table[startNode] != 1) return dp[startNode][K] = 0;
      return dp[startNode][K] = 1.0;
   }
   double res = 0.0;
   int poss = adjlist[startNode].size();
   for (int i = 0; i < adjlist[startNode].size(); i++) {
      res += (1.0 / poss) * calcPr(adjlist[startNode][i], K-1);
   }
   return dp[startNode][K] = res;
}

Now, we have finished the first step of the problem. The second step involves calculating out of the many possible landings we have chosen and given that we did arrive home safely, what is the probability we chose startLanding? The easiest way to think of this is to think geometrically. If we let a circle C be the total sum of the probabilities that we arrived safely from all possible landings, we can scale this to 1.0 as we know for certainty that we arrived safely (given in the problem). Now we simply need to calculate how much probability was contributed by starting from startLanding. This is simply calcPr(startLanding, K) / totalSum. This can be visualised as:

double tot = 0.0;
for (int i = 0; i < 51; i++) for (int j = 0; j < 51; j++) dp[i][j] = -1.0;
for (int i = 0; i < landings.size(); i++) {
   tot += calcPr(i, K);
}
return calcPr(startLanding, K) / tot;

Combining all of the above steps, we yield the final code:

class ParkAmusement {
public:
   double getProbability(vector <string>, int, int);
};

vector<vector<int> > adjlist;
int table[51];
double dp[51][51];

double calcPr(int startNode, int K) {
   if (dp[startNode][K] >= 0.0) return dp[startNode][K];
   if (K == 0) {
      if (table[startNode] != 1) return dp[startNode][K] = 0;
      return dp[startNode][K] = 1.0;
   }
   double res = 0.0;
   int poss = adjlist[startNode].size();
   for (int i = 0; i < adjlist[startNode].size(); i++) {
      res += (1.0 / poss) * calcPr(adjlist[startNode][i], K-1);
   }
   return dp[startNode][K] = res;
}

double ParkAmusement::getProbability(vector <string> landings, int startLanding, 
      int K) {
   adjlist = vector<vector<int> >(landings.size(), vector<int>());
   for (int i = 0; i < landings.size(); i++) {
      if (landings[i][i] != '0') {
         // exit
         if (landings[i][i] == 'P') table[i] = 2;   // pond
         else table[i] = 1; // exit
         continue;
      }
      for (int j = 0; j < landings[i].size(); j++) {
         if (landings[i][j] == '1') adjlist[i].push_back(j);
      }
   }
   double tot = 0.0;
   for (int i = 0; i < 51; i++) for (int j = 0; j < 51; j++) dp[i][j] = -1.0;
   for (int i = 0; i < landings.size(); i++) {
      tot += calcPr(i, K);
   }
   return calcPr(startLanding, K) / tot;
}