0452HardArrayMathDynamic ProgrammingMinimaxGame TheoryZero-Sum Game

Clearing The Salvage Row

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two graders, Iris and Otto, clear a row of salvaged crates. merits[i] is the signed merit of the crate standing i places from the head of the row: a damaged crate carries a negative merit and still counts against whoever takes it.

Iris goes first and the two then alternate. On a turn the grader on duty takes the first one, two or three crates still standing, in a single block from the head of the row, and adds their merits to a personal score. A turn must take at least one crate, and the row shortens as it goes, so the last grader to move may have fewer than three left to choose from. Play ends when the row is empty.

Both graders know the whole row from the start and both play to finish with the largest personal score they can force, caring about nothing else.

Return "Iris" if she ends with the larger score, "Otto" if he does, and "Draw" if the two scores are level.

Examples

Example 1

Input: merits = [5, -2, 8, 40, -6]
Output: "Otto"

One line runs: Iris clears 5, -2 and 8, Otto clears 40, and Iris is left with the crate at -6. That ends 5 against 40, so the second grader has the larger score.

Example 2

Input: merits = [7, 7, 7, 7]
Output: "Iris"

Iris clears three crates for 21 and the single crate left hands Otto 7.

Example 3

Input: merits = [-11, -11, 22]
Output: "Draw"

Iris clears all three crates in one turn and finishes on 0, and Otto never gets a move, so he finishes on 0 too.

Constraints

1 <= merits.length <= 5 * 10^4
-1000 <= merits[i] <= 1000

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def salvage_winner(merits: list[int]) -> str:

Java

public String salvageWinner(int[] merits)

The intended approach

Time O(n) for n crates: each starting point weighs three blocks.Space O(1) beyond the input, since three running leads replace the table.

Work backwards along the row, recording for each starting point the largest lead the grader on duty can force over the other from that point on. A turn that takes a block of crates scores that block and then hands the rest over, so it is worth the block's merit minus the lead the reply can force. Only the three positions just past the current one are ever consulted, so three running values replace the whole table, and the sign of the value at the head of the row names the winner.

Pythonentry point: salvage_winner

def salvage_winner(merits):
    # Sweep the row from the far end holding, for each starting point, the best
    # lead the player to move can force from there. Only three later positions
    # are ever needed, so three running values suffice.
    # O(n) time, O(1) extra space.
    n = len(merits)
    lead1 = lead2 = lead3 = 0
    for i in range(n - 1, -1, -1):
        later = (lead1, lead2, lead3)
        best = None
        haul = 0
        for k in range(3):
            if i + k >= n:
                break
            haul += merits[i + k]
            cand = haul - later[k]
            if best is None or cand > best:
                best = cand
        lead3, lead2, lead1 = lead2, lead1, best
    if lead1 > 0:
        return "Iris"
    if lead1 < 0:
        return "Otto"
    return "Draw"

The obvious version

Search the whole game tree with no bookkeeping: from each position try all three block sizes and return the best lead, recursing on the rest of the row. Exponential in the row length.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_salvage_winner(merits):
    n = len(merits)

    def explore(i):
        if i >= n:
            return 0
        best = None
        haul = 0
        for k in range(3):
            if i + k >= n:
                break
            haul += merits[i + k]
            cand = haul - explore(i + k + 1)
            if best is None or cand > best:
                best = cand
        return best

    lead = explore(0)
    if lead > 0:
        return "Iris"
    if lead < 0:
        return "Otto"
    return "Draw"

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in