Game Theory in Competitive Programming Part — 8

CSES Removal Game

Mar 22 · 3 min read

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?

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:

Intellectually Yours

Game Theory is everywhere. Everywhere.

Intellectually Yours

A publication that focuses on applications of game theory and strategy in real life — around us. This publication is maintained by The Indian Game Theory Society — DTU which focuses on educating people about game theory in real life.

Written by

Intellectually Yours

A publication that focuses on applications of game theory and strategy in real life — around us. This publication is maintained by The Indian Game Theory Society — DTU which focuses on educating people about game theory in real life.

I Switched to Lite After Using Visual Studio Code for 3 Years

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app