Growing Grab Game
Problem
Two players share a row of stone piles piles. A number M starts at 1. Players alternate, the first player starting. On a turn, the player takes all stones from the first X remaining piles, for some 1 ≤ X ≤ 2M, and then M becomes max(M, X).
The game ends when no piles remain. Both players play to maximise their own total. Return the number of stones the first player collects.
Example 1
- Input:
- piles = [3, 8, 2, 5, 4]
- Output:
- 11
Taking only [3] lets the opponent take [8] and keep control, leaving the first player with 10. Taking [3, 8] (X = 2, M becomes 2) gives the opponent everything left (2 + 5 + 4 = 11), but the first player still has 11, which is the best possible.
Example 2
- Input:
- piles = [4, 1, 1]
- Output:
- 5
Take [4, 1] with X = 2; the opponent gets the last 1.
Example 3
- Input:
- piles = [6]
- Output:
- 6
Constraints
- 1 ≤ piles.length ≤ 100
- 1 ≤ piles[i] ≤ 10^4
Hint
Show the first hint
A position is described by where the remaining piles start and the current value of M. Nothing else matters.
Walkthrough
How to approach it
01Clarify before coding
- Must the player take the first X piles, not any X? Yes, always from the front of what remains.
- Does M ever decrease? No, it only grows to max(M, X).
- Do both players maximise their own stones? Yes, and since the total is fixed, that is also minimising the opponent's.
02Brute force
Recurse over the full game tree, trying every X at every turn.
Cost: Exponential: the branching factor 2M grows during the game, and the same (start, M) positions are revisited endlessly.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.