Skip to content

Removal Game

  • Title: Removal Game
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1097
  • Secondary topics: Score-difference DP, Take from ends game, Minimax
  • Difficulty: medium
  • Subtype: Optimal play on an interval where each move removes one end
  • Status: solved
  • Solution file: removalgame.cpp

Why Practice This

This is one of the cleanest interval-DP games in the standard curriculum:

  • every state is just a subarray [l, r]
  • each move removes either the left end or the right end
  • the opponent immediately faces another interval of the same form

It is also a great example of a useful DP modeling trick: instead of storing the absolute score of the first player, store the score difference between the current player and the other player. That turns a minimax-looking game into a short recurrence.

Recognition Cue

Reach for interval DP here because:

  • the remaining game state is always one contiguous interval
  • each move removes one endpoint
  • after one move, the opponent faces the same kind of interval state
  • brute-force minimax branches exponentially, but the subproblems repeat heavily

The special modeling smell is:

  • a two-player take-from-ends game often gets much cleaner if you store score difference instead of absolute score

Problem-Specific Transformation

The raw statement sounds like game theory, but the reusable rewrite is:

  • state = current remaining interval [l, r]
  • value = best achievable (current player score - other player score)

That transformation removes the need to alternate explicit "max for me / min for opponent" logic. After taking one end, the opponent's optimal response is already summarized by the same DP on the smaller interval, so the recurrence becomes subtraction against a reused subproblem.

Core Idea

Let:

dp[l][r] = maximum possible (current player's score - other player's score)
           when the remaining numbers are a[l..r]

If the current player takes the left end a[l], then the opponent becomes the "current player" on interval [l + 1, r], so the net advantage is:

a[l] - dp[l + 1][r]

If the current player takes the right end a[r], the net advantage is:

a[r] - dp[l][r - 1]

So the recurrence is:

dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])

Base case:

dp[i][i] = a[i]

because with one number left, the current player just takes it.

Once we know the final difference diff = dp[0][n - 1], recover the first player's actual score using:

first + second = total_sum
first - second = diff

Therefore:

first = (total_sum + diff) / 2

The implementation below compresses the interval DP to one dimension. Iterate l from right to left, and for each fixed l, sweep r from l + 1 to n - 1. Then:

  • the old dp[r] still means dp[l + 1][r]
  • the already updated dp[r - 1] means dp[l][r - 1]

That gives the same recurrence in O(n) memory.

Complexity

  • states: O(n^2)
  • transition per state: O(1)
  • total: O(n^2)
  • memory: O(n) with the compressed implementation

This is the intended complexity for the CSES constraints.

Pitfalls / Judge Notes

  • dp[l][r] is a difference, not the first player's score directly.
  • The transition uses subtraction because after taking one end, the opponent gets the next move.
  • Use long long; sums can grow well beyond int.
  • For the 1D compression, the loop order matters: l must go downward, and r must go upward.

Reusable Pattern

  • Topic page: Interval DP
  • Practice ladder: Interval DP ladder
  • Starter template: interval-dp.cpp
  • Notebook refresher: DP cheatsheet
  • Carry forward: decide what interval [l, r] means and which smaller intervals feed it.
  • This note adds: the score function and move order that make this interval recurrence work.

Solutions