Stone Game VIII

Stone Game VIII

What is this problem about?

Stone Game VIII is a "Hard" game where Alice and Bob take turns taking $x$ stones from the beginning of a row (where $x > 1$). The player receives points equal to the sum of the $x$ stones taken. These $x$ stones are then replaced by a single stone whose value is equal to their sum. The game ends when only one stone remains.

Why is this asked in interviews?

Infosys uses this problem to see if a candidate can optimize a complex-sounding game into a simple linear-time solution. It requires you to notice that every "new" stone created is actually a prefix sum of the original array. This mathematical insight allows you to transform an $O(N^2)$ DP into an $O(N)$ one.

Algorithmic pattern used

The pattern is Dynamic Programming and Prefix Sums.

1. Calculate the prefix sum array pre.
2. Notice that if a player takes $x$ stones, they get pre[x-1] points, and the next player will choose some $y > x$ and get pre[y-1] - ....
3. Let dp[i] be the maximum relative score a player can get if they must pick at least $i$ stones.
4. dp[i] = max(dp[i+1], pre[i] - dp[i+1]). This allows us to solve the problem in a single backward pass from $N-1$ down to 1.

Example explanation (use your own example)

Piles: [-10, -5, 0, 5, 10]. Prefix sums: [-10, -15, -15, -10, 0].

• A player can take 2, 3, 4, or 5 stones.
• If Alice takes 2 stones, she gets -15 points. The new pile is [-15, 0, 5, 10].
• However, since every move results in a new stone that is just a prefix sum, the actual value of the stone doesn't matter as much as the value of the prefix sum at that index. We start from the end and work backward to find the best possible relative score Alice can achieve.

Common mistakes candidates make

• Simulating the "replacement": Actually trying to modify the array, which is slow and complicated.
• Ignoring the $x > 1$ rule: Forgetting that Alice cannot take just the first stone in her first move.
• Complexity: Attempting a cubic or quadratic DP when a linear one is possible.
• Prefix sum errors: Especially when the array contains negative numbers.

Interview preparation tip

Always look for what remains constant in a problem. In Stone Game VIII, the sum of stones taken is always a prefix sum of the original array. This realization is the key to moving from a Hard problem to a straightforward linear DP.