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