USACO Training Gateway - "A Game"

Problem Statement:

"Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alternately by selecting a number from either the left or the right end of the sequence. That number is then deleted from the board, and its value is added to the score of the player who selected it. A player wins if his sum is greater than his opponents.

Write a program that implements the optimal strategy. The optimal strategy yields maximum points when playing against the "best possible" opponent. Your program must further implement an optimal strategy for player 2."

Strategy:

This is a simple dynamic programming problem which involves the theme about games (two players) which is quite common. As no number in the sequence can be skipped, it is sufficient enough to compute one player's score and derive the other player's score by subtracting it from the total sum of the sequence on the board. This allows us to condense our DP state by a factor of 2 by keeping track of only one player's progress.

As with all DP problems we first define the DP state. Here an obvious one can be defined as:

D(n,m) = the best score for player 1 in which the board state is a contiguous subsequence between index n and m. Player 1's turn.
E(n,m) = the best score for player 1 in which the board state is a contiguous subsequence between index n and m. Player 2's turn.

As the maximum board size is only 100, an O(n^2) space complexity easily fits within the memory limits. Next we define our recurrence relation:

For the current player we can choose either the leftmost or the rightmost block, i.e. A[n] or A[m]. The next turn in the game is player 2's turn which is denoted by the E(x,y) relation. The obvious goal of player 2 is to minimise the gain of player 1 which will result in a higher score for him/herself.

Using the two recurrences we can combine them into one to get (using direct substitution from E(n,m) to D(n,m)):

Hence, we have constructed our recurrence for player 1. We keep track of the total sum of the sequence of the board during the input/parsing phase. Player 2's score is simply total sum - D(0, size-1). Lastly, we need to handle our base cases. If n = m, then we are left with one choice - choosing A[n]. If n > m, which means we have finished the game as the current board state is non-existent, then we return 0 as neither player can choose any more integers from the sequence. Hence explicitly the base cases are:

Implementation:

Using the idea above we generate the simple memoisation algorithm:

int dp[101][101];
vector<int> vec;

int func(int n, int m) {
   if (n > m) return 0;
   if (n == m) return dp[n][m] = vec[n];
   if (dp[n][m] != -1) return dp[n][m];
   int res = 0;
   res = max(min(func(n+2,m),func(n+1,m-1))+vec[n],
      min(func(n+1,m-1),func(n,m-2))+vec[m]);
   return dp[n][m] = res;
}

int main() {
   ifstream inFile("game1.in");
   ofstream outFile("game1.out");
   int N; inFile >> N;
   int sum = 0;
   for (int c = 0; c < N; c++) {
      int val; inFile >> val;
      sum += val;
      vec.push_back(val);
   }
   memset(dp,-1,sizeof(dp));
   outFile << func(0,N-1) << " " << sum - func(0,N-1) << "\n";
   return 0;
}

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;
}

Applications of Floyd-Warshall's Algorithm

We will expand on the last post on Floyd-Warshall's algorithm by detailing two simple applications. The first is using the algorithm to compute the transitive closure of a graph, the second is determining whether or not the graph has a negative cycle.

Transitive closure is simply a reachability problem (in terms of graph theory) between all pairs of vertices. So if we compute the transitive closure of a graph we can determine whether or not there is a path from vertex x to vertex y in one or more hops. Unlike the shortest path problem we aren't concerned on how long it takes to get there, only whether or not if we can eventually get there. Obviously you can simply not modify our original algorithm and assume if the distance between vertex x to vertex y is at least "infinity" then there is no way to get from vertex x to vertex y, otherwise there is a way to get there. This perfectly solves the reachability problem.

There is cleaner approach of computing the transitive closure using a slight modification of Warshall's algorithm. Instead of letting no edge between x to y be denoted by infinity, we can let it be 0 (or false). Any weighted edge is simply reduced to 1 (or true). Now instead of adding distances we use the binary-AND operation. If graph[x][k] is true and graph[k][y] is also true, then there is a way to connect x to y. Any other combination will result in failing to connect vertex x to vertex y using an intermediate node k. So graph[x][k] & graph[k][y] correctly fits our desired behaviour. As we just need 1 such intermediate node k to connect vertex x to vertex y, we combine it with the binary-OR operation as we don't care which intermediate vertex it requires to get from x to y so long as there is a path that allows us to get there.

The modified algorithm is the following:

// warshall's algorithm for transitive closure
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
         // only need one connection for it to be reachable, hence the 
         //    OR operation.
         // need both adjmat[i][k] and adjmat[k][j] to be connected for i to go 
         //    to j using intermediate node k.
         adjmat[i][j] |= (adjmat[i][k] & adjmat[k][j]);
      }
   }
}
// post-condition if adjmat[i][j] is 1 then there is a path from vertex i to j

We can make an obvious small optimisation by only running the inner loop if adjmat[i][k] is true, otherwise all the inner computations would fail anyway.

// warshall's algorithm for transitive closure - attempt 2
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      // optimise here by reducing the number of inner loops
      if (adjmat[i][k]) {
         for (int j = 1; j <= N; j++) {
            adjmat[i][j] |= (adjmat[i][k] & adjmat[k][j]);
         }
      }
   }
}
// post-condition if adjmat[i][j] is 1 then there is a path from vertex i to j

The second application is using it to detect negative cycles in a graph. How does Floyd-Warshall relate to this? Since the algorithm calculates the shortest path between all pairs of vertices we can use the "shortest path" for vertex i to itself to determine if there is a cycle. If we can reach from vertex i to itself with a cost less than 0 then we can keep looping through to successively generate shorter paths - hence the term negative cycle. Therefore it is sufficient to just check whether or not adjmat[i][i] < 0 for all vertices. This is used in many other algorithms such as the cycle-cancelling algorithm for minimum cost flows.

// warshall's algorithm for detecting negative cycles
bool cycle = false;
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
         adjmat[i][j] = min(adjmat[i][j], adjmat[i][k] + adjmat[k][j]);
      }
      if (adjmat[i][i] < 0) cycle = true;
   }
}

Floyd-Warshall All-Pairs Shortest Path Algorithm

There are many notable algorithms to calculate the shortest path between vertices in a graph. Most are based on single source to a set of destination vertices. Examples of such famous algorithms include Dijkstra's, Bellman-Ford and even breadth first search for weightless graphs. However, sometimes we wish to calculate the shortest paths between all pairs of vertices. An easy way to calculate this is to loop through each possible pair of vertices and run a Dijkstra through it. However, there exists a more efficient way to calculate this in n^3 time complexity.

The basis of this algorithm lies with dynamic programming. As with all dynamic programming algorithms we need to first define the DP state. The key factor in this algorithm is to consider an intermediate node k of which to connect two vertices i and j. We check if the path from i to k and then from k to j improves our current shortest path length from vertex i to j. If it does, we update - otherwise we don't. Using this definition our DP state becomes:

D(i,j,k) = shortest path length from vertex i to j considering a set of intermediate nodes from vertex 1 to k

We don't need to explicitly label our vertices as this is done implicitly through our algorithm. Now we need to define our recurrence relation. For a given instance of D(i,j,k) we can calculate the shortest path by considering all intermediate vertices from 1 to k. The proposed distance is easily calculated as D(i,k,k-1) + D(k,j,k-1) by definition of an intermediate node. Formally,

F(i,j,k) = min { F(i,j,k-1), F(i,k,k-1) + F(k,j,k-1) }

We have to determine whether or not the new intermediate node k actually helps achieve a shortest path by comparing it to the previous computation without considering intermediate node k, i.e. F(i,j,k-1).

As with all recurrence relations, a base case is required. If we don't consider any intermediate nodes at all, then the shortest path between two vertices is simply the direct edge between vertex i and j. In other words, the weight of the (i,j) entry in the adjacency matrix. So now we have fully defined our recurrence relation with the proper base case:

F(i,j,k) = min { F(i,j,k-1), F(i,k,k-1) + F(k,j,k-1) }
F(i,j,0) = w(i,j)

To calculate this in a bottom-up manner is actually quite simple. First we note the order dependency of the recurrence relation. It can be seen that a particular instance D(i,j,k) can depend on D(i,0,k-1) to D(N,j,k-1) where N is the number of vertices. So it's obvious we need to compute the previous intermediate k values first (i.e. 1, 2, .., k-1 before calculating k). The order of i and j does not matter in our case because we would have computed all k-1 (i,j) pairs before. Using this information we yield an extremely elegant solution:

// warshall's algorithm
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
         adjmat[i][j] = min(adjmat[i][j], adjmat[i][k] + adjmat[k][j]);
      }
   }
}

Let's apply this algorithm to a simple graph theory problem.

TopCoder SRM 301 D1-450 (EscapingJail)
URL: http://www.topcoder.com/tc?module=ProblemDetail&rd=9822&pm=6222

The problem states there are a set of prisoners chained up and we need to determine the maximum distance that a pair of prisoners can be from each other. It's obvious that the maximum length that two prisoners can be apart is defined by the shortest chain separating a connected path between the two prisoners. Sound familiar? This is the exact definition of a shortest path problem! We simply need to find the shortest distance between every pair of prisoner and calculate the maximum of all such pairs.

How do we handle cases in which the prisoners are not chained together (i.e. there is no edge between them)? We can set a sentinel value to denote that the prisoners aren't chained, if we set this to 0 it would be wrong because then it would interfere with our minimum distance calculation. A simple option is to set this to a high/infinity value and if we know the distance from prisoner i to prisoner j exceeds or equals this value then we know they are unbounded. For this problem, we need to return a value of -1 for unbounded distance.

The only remaining part of the problem is translating the given string array into the adjacency matrix. This is a simple exercise of converting a character into the suitable value - if it's a space then we set the distance to be infinity since they aren't chained together. All that leaves is to use the Warshall algorithm and compute the maximum of the pairs (and remembering to return -1 if the distance between at least two prisoners is unbounded).

The implementation is as follows:

class EscapingJail {
public:
   int getMaxDistance(vector <string>);
};

#define INF (1 << 27)

int translate(char ch) {
   if (isdigit(ch)) return ch - '0';
   if (islower(ch)) return ch - 'a' + 10;
   if (isupper(ch)) return ch - 'A' + 36;
   return INF;
}

int adjmat[51][51];

int EscapingJail::getMaxDistance(vector <string> chain) {
   int res = 0;
   for (int i = 0; i < chain.size(); i++) {
      for (int j = 0; j < chain[i].size(); j++) {
         adjmat[i][j] = translate(chain[i][j]);
      }
   }
   for (int k = 0; k < chain.size(); k++) {
      for (int i = 0; i < chain.size(); i++) {
         for (int j = 0; j < chain.size(); j++) {
            adjmat[i][j] = min(adjmat[i][j], adjmat[i][k] + adjmat[k][j]);
         }
      }
   }
   for (int i = 0; i < chain.size(); i++) {
      for (int j = 0; j < chain.size(); j++) {
         if (i == j) continue;
         if (adjmat[i][j] >= INF) return -1;
         res = max(res, adjmat[i][j]);
      }
   }
   return res;
}