Game Theory in Competitive Programming Part — 8
CSES Removal Game
Welcome to part 8 of this series, in case you have missed part 7, here is the link: Part 7
Problem Statement:
There is a list of n numbers and two players who move alternately. On each move, a player removes either the first or last number from the list, and their score increases by that number. Both players try to maximize their scores.
What is the maximum possible score for the first player when both players play optimally?
Problem Link: https://cses.fi/problemset/task/1097
Input
The first input line contains an integer n: the size of the list.
The next line has n integers x[1], x[2], … x[n]: the contents of the list.
Output
Print the maximum possible score for the first player.
Constraints
- 1 ≤ n ≤ 5000
- −10⁹ ≤ x[i] ≤ 10⁹
Example
Input:
4
4 5 1 3
Output:
8
Explanation
You first pick up the 3 value coin at the end. Your opponent proceeds to pick up the 4 value coin, after which you get the +5 coin and your opponent picks up the remaining +1 coin. This yields you a score of 8 and your opponent a score of 5. No other selection will yield a higher score for you.
Does Greedy Work?
The first approach you think of is a greedy one, where you take whichever coin out of the ones at each end has higher value. However, it’s easy to see why this would fail. For a coin you pick, it’s possible you enable your opponent to pick a much more valuable coin. Eg:
5 100 1 3
Greedily, you would pick the +5 coin, but that would enable your opponent to pick the +100 coin, bringing you to a final score of 8 (5 + 3) and your opponent to 101 (100 + 1). The best case for the first player here is 103 (3 + 100) to 6 (5 + 1).
This is where we introduce dynamic programming to our solution.
Dynamic Programming:
Explanation of the State:
For our dynamic programming solution, we maintain a state scores[i][j] which contains a pair of integers {first,second}, where first denotes the best score of the player moving first, and second is the best score for the player moving second, for a game with the coins in the range i to j (both inclusive). So for example, scores[2][5] = {8,3} means for a game using the coins in the 2nd position through to the 5th position, the first player’s optimal score is 8 and the second’s player’s best score with that move would be 3.
Calculating the Base Scores:
For the cases where i=j, we only have one coin. This means whoever moves first gets to pick up that coin, thus scores[i][i] = {coins[i],0}.
Now we switch to dynamic programming to calculate the rest of the scores.
Populating the Rest of the Scores:
At each step for scores[i][j], the player has two options: either pick the coin at i or the coin at j. If he picks the coin at i, his score would be coins[i] + scores[i+1][j].second. This is because after his move, he becomes the second player. Similarly, if he picks the coin at j, his score would be coins[j] + scores[i][j-1].second.
Since the player moving gets to decide, he picks whichever is the better option. Thus, if he picks the coin at i, the second player’s score would be scores[i+1][j].first, and in case j was picked, his score would be scores[i][j-1].first.
Thus formally,
if (coins[i] + scores[i+1][j].second >= coins[j] + scores[i][j-1].second) scores[i][j] = {coins[i] + scores[i+1][j].second, scores[i+1] [j].first};
else scores[i][j] = {coins[j] + scores[i][j-1].second, scores[i][j-1].first};
One important observation is that to calculate scores[i][j], we must already have calculated scores[i+1][j] as well as scores[i][j-1]. Thus for our solution we will calculate scores in an increasing order of length of the range, meaning after we calculate our base cases (i=j), we calculate for all j=i+1, then for j=i+2 and so on.
Our final answer would be the best score (since our player moves first) for the complete range, ie 1…n
With the formula and base cases in place, we get to coding our solution.
Code:
