Stone Game VI

medium dp greedy sorting game theory

Problem

Alice and Bob take turns picking stones (Alice first). Stone i is worth aliceValues[i] to Alice and bobValues[i] to Bob. Each plays optimally to maximize their own total. Return 1 if Alice wins, -1 if Bob wins, 0 if a tie.

InputaliceValues = [1,3], bobValues = [2,1]

Output1

Sort stones by alice[i] + bob[i] descending. Alice takes the odd positions of that order, Bob the even ones.

aliceValues

bobValues

def stone_game_vi(aliceValues, bobValues):
    n = len(aliceValues)
    order = sorted(range(n), key=lambda i: -(aliceValues[i] + bobValues[i]))
    a, b = 0, 0
    for turn, i in enumerate(order):
        if turn % 2 == 0:
            a += aliceValues[i]
        else:
            b += bobValues[i]
    return (a > b) - (a < b)

function stoneGameVI(aliceValues, bobValues) {
  const n = aliceValues.length;
  const order = [...Array(n).keys()];
  order.sort((x, y) => (aliceValues[y] + bobValues[y]) - (aliceValues[x] + bobValues[x]));
  let a = 0, b = 0;
  order.forEach((i, turn) => {
    if (turn % 2 === 0) a += aliceValues[i];
    else b += bobValues[i];
  });
  return a > b ? 1 : a < b ? -1 : 0;
}

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (x, y) ->
            (aliceValues[y] + bobValues[y]) - (aliceValues[x] + bobValues[x]));
        long a = 0, b = 0;
        for (int turn = 0; turn < n; turn++) {
            if (turn % 2 == 0) a += aliceValues[order[turn]];
            else b += bobValues[order[turn]];
        }
        return Long.compare(a, b);
    }
}

int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
    int n = aliceValues.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) {
        return aliceValues[x] + bobValues[x] > aliceValues[y] + bobValues[y];
    });
    long long a = 0, b = 0;
    for (int turn = 0; turn < n; turn++) {
        if (turn % 2 == 0) a += aliceValues[order[turn]];
        else b += bobValues[order[turn]];
    }
    return (a > b) - (a < b);
}

Explanation

Each turn a player removes a stone, and crucially that stone is gone for both players. So when Alice takes stone i she gains alice[i] and at the same time denies Bob the bob[i] he would have scored. The true worth of a stone to whoever grabs it is therefore alice[i] + bob[i].

This turns the game into a simple greedy: sort the stones by alice[i] + bob[i] in descending order. Players alternate down this list, Alice taking positions 0, 2, 4… and Bob taking positions 1, 3, 5….

Why is the greedy optimal? An exchange argument: if the current player skipped the highest combined stone for a lower one, swapping the two choices never decreases the gap in their favour. So always grabbing the largest combined value is a dominant strategy.

We do not even need to simulate "scores"; we just add alice[i] to Alice's total on her turns and bob[i] to Bob's on his, then compare the two totals at the end and return the sign of the difference.

Example: alice = [1,3], bob = [2,1]. Combined values are [3, 4], so stone 1 (combined 4) is taken first by Alice for 3, then stone 0 by Bob for 2. Alice 3 > Bob 2, so the answer is 1.

Time: O(n log n) Space: O(n)