Stone Game V

Stone Game V

What is this problem about?

Stone Game V is a "Hard" difficulty problem where Alice and Bob play a game by splitting a row of stones into two parts. Alice chooses the split point. Bob then looks at the sums of the two parts and discards the part with the larger sum. Alice gets the points from the part that remains. If the sums are equal, Alice gets to choose which part to keep. The game continues until only one stone remains.

Why is this asked in interviews?

Google uses this problem to test a candidate's mastery of Dynamic Programming on intervals. It requires you to consider all possible split points for every possible subarray. It assesses your ability to optimize a cubic $O(N^3)$ DP solution using Prefix Sums and, potentially, more advanced techniques like pre-calculating optimal split points.

Algorithmic pattern used

The core Algorithmic pattern is Interval Dynamic Programming.

• State: dp[i][j] represents the maximum score Alice can get from the subarray piles[i...j].
• Transition: For every possible split point $k$ from $i$ to $j-1$:
  • If sum(i, k) < sum(k+1, j), Alice gets sum(i, k) + dp[i][k].
  • If sum(i, k) > sum(k+1, j), Alice gets sum(k+1, j) + dp[k+1][j].
  • If equal, she gets max(sum(i, k) + dp[i][k], sum(k+1, j) + dp[k+1][j]). Prefix sums are used to calculate the sum of any interval in $O(1)$.

Example explanation (use your own example)

Piles: [6, 2, 3, 4, 5, 5].

• Alice splits into [6, 2, 3] (sum 11) and [4, 5, 5] (sum 14).
• Bob discards [4, 5, 5] because 14 > 11.
• Alice gets 11 points and now plays with [6, 2, 3].
• Alice must find the split point for [6, 2, 3] that maximizes her future score. She could split it into [6] (sum 6) and [2, 3] (sum 5). Bob would discard [6], and she'd get 5 more points.

Common mistakes candidates make

• Naive sum calculation: Recalculating the sum of parts in every recursive call instead of using a Prefix Sum array.
• Missing the "equal sum" case: Forgetting that Alice gets to choose the best part if the sums are equal.
• TLE (Time Limit Exceeded): Failing to use memoization, resulting in an exponential time complexity.
• Over-optimization: Trying to use techniques like Knuth's optimization which don't apply here, instead of focusing on the core interval DP.

Interview preparation tip

Practice "Interval DP" problems where you build the solution for smaller subarrays and use them to find the solution for larger ones. This Stone Game V interview question is a textbook example of this pattern.