Stone Game VI

Stone Game VI

What is this problem about?

In Stone Game VI, Alice and Bob are given two arrays representing the values they each assign to a set of stones. They take turns picking a stone. Alice wants to maximize her total value minus Bob's total value, and Bob wants to minimize that difference. Each player picks optimally.

Why is this asked in interviews?

This problem, often seen at Arcesium, tests your ability to identify a Greedy interview pattern in a Game Theory context. The core challenge is realizing that the "value" of a stone isn't just what it gives you, but also what it takes away from your opponent.

Algorithmic pattern used

The pattern is Greedy and Sorting. The "true value" of a stone at index $i$ for either player is aliceValues[i] + bobValues[i]. Why? Because by picking stone $i$, Alice gains aliceValues[i] and prevents Bob from getting bobValues[i]. The total "swing" in the relative score is the sum of both values. Both players should always pick the stone with the largest aliceValues[i] + bobValues[i] first.

Example explanation (use your own example)

Stones values: Alice: [1, 3], Bob: [2, 1].

• Stone 0: Alice+Bob = 3.
• Stone 1: Alice+Bob = 4. Alice goes first. If she picks Stone 0, she gets 1 point. Bob then picks Stone 1 and gets 1 point. Score: 1-1 = 0. If she picks Stone 1, she gets 3 points. Bob then picks Stone 0 and gets 2 points. Score: 3-2 = 1. Alice picks Stone 1 because the sum (4) is higher than Stone 0's sum (3).

Common mistakes candidates make

• Picking by Alice's value only: Alice picking her highest value stone without considering what Bob would get.
• Complex DP: Trying to solve this with dynamic programming, which is $O(2^N)$ and unnecessary when a simple $O(N \log N)$ sorting approach exists.
• Heap misuse: Using two separate heaps for Alice and Bob, which doesn't account for the combined value of the stones.

Interview preparation tip

When two players are competing for the same resources with different values, the optimal strategy often involves maximizing the "combined benefit" or "opportunity cost." This Stone Game VI coding problem is a classic example.