Stone Game III

HARD✓ CHIP-TIMEDLC #1406 — FULL STATEMENT ↗

The drill: Two players alternate taking 1, 2, or 3 stones off the FRONT of a row (values can be negative), both playing to maximize their own total. Report who wins — Alice moves first, and ties are possible.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of stone values, which can include negative numbers, sits between two players — Alice moving first, then Bob — who alternate taking 1, 2, or 3 stones off the front of what remains. Each player is trying to maximize their own running total, not merely deny the other side.

Every stone taken counts toward whichever player took it; there's no discarding or passing. Since values can be negative, taking stones isn't always good — an optimal player sometimes has to swallow a bad stretch because every alternative is worse.

The result is which side comes out ahead once the whole row is gone under both players' best play — Alice, Bob, or a tie when their totals land exactly equal.

EX 01

stoneValue = [2, 4, 1, 9]

→ "Bob"

BOB'S FORCED LAST GRAB OUTWEIGHS ALICE'S EARLY LEAD

EX 02

stoneValue = [3, 1, 2, -8]

→ "Alice"

THE TRAILING NEGATIVE IS WORTH DUMPING ON BOB

EX 03

stoneValue = [-2, 2, -4, 4]

→ "Tie"

A NON-TRIVIAL TIE, NO ZEROS INVOLVED

stone values can be negative, zero, or positive
each turn takes exactly 1, 2, or 3 stones from the front
Alice always moves first
the result names the winner or reports a tie, not a numeric score

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

This isn't about total stones taken, it's about the score gap a player can force. What's the best score-difference (mine minus theirs) achievable starting from some position in the row?

HINT 2 THE STRUCTURE

diff(i) = the best a player starting at i can do relative to whoever moves after them. Taking k stones nets those k values, then SUBTRACTS the best the opponent can force from i + k onward — because the opponent plays optimally too.

HINT 3 ONE STEP FROM THE ANSWER

diff(i) = max over k in {1,2,3} of (sum of stones[i..i+k-1]) − diff(i+k), built backward from the empty row where diff(n) = 0. The sign of diff(0) alone decides Alice, Bob, or Tie.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SCORE GAPPATTERN · SCORE-GAP DPstoneValue = [3, 1, 2, -8]

-8

SCORE GAP AT EACH START

— empty —

STEP 1

diff(i) is the best score gap the mover starting at i can force over their opponent. diff(4) = 0 for the empty row.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/stone-game-iii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        diff = [0] * (n + 1)  # diff[i] = best score gap achievable starting at i
        for i in range(n - 1, -1, -1):
            best = float("-inf")
            running = 0
            for k in range(1, 4):
                if i + k - 1 >= n:
                    break
                running += stoneValue[i + k - 1]
                best = max(best, running - diff[i + k])
            diff[i] = best

        if diff[0] > 0:
            return "Alice"
        if diff[0] < 0:
            return "Bob"
        return "Tie"

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 19 LN

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)

        def diff(i: int) -> int:
            if i >= n:
                return 0
            best = float("-inf")
            running = 0
            for k in range(1, 4):
                if i + k - 1 >= n:
                    break
                running += stoneValue[i + k - 1]
                best = max(best, running - diff(i + k))  # net gain minus opponent's best reply
            return best

        result = diff(0)
        if result > 0:
            return "Alice"
        if result < 0:
            return "Bob"
        return "Tie"

TIME O(3ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] diff = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int best = Integer.MIN_VALUE;
            int running = 0;
            for (int k = 1; k <= 3; k++) {
                if (i + k - 1 >= n) {
                    break;
                }
                running += stoneValue[i + k - 1];
                best = Math.max(best, running - diff[i + k]);
            }
            diff[i] = best;
        }
        if (diff[0] > 0) {
            return "Alice";
        }
        if (diff[0] < 0) {
            return "Bob";
        }
        return "Tie";
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 25 LN

class Solution {
    private int[] stoneValue;
    private int n;

    public String stoneGameIII(int[] stoneValue) {
        this.stoneValue = stoneValue;
        this.n = stoneValue.length;
        int result = diff(0);
        if (result > 0) {
            return "Alice";
        }
        if (result < 0) {
            return "Bob";
        }
        return "Tie";
    }

    private int diff(int i) {
        if (i >= n) {
            return 0;
        }
        int best = Integer.MIN_VALUE;
        int running = 0;
        for (int k = 1; k <= 3; k++) {
            if (i + k - 1 >= n) {
                break;
            }
            running += stoneValue[i + k - 1];
            best = Math.max(best, running - diff(i + k));
        }
        return best;
    }
}

TIME O(3ⁿ)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED