0331MediumArrayMathDynamic ProgrammingMinimaxGame TheoryZero-Sum Game

Shelf End Bidding Duel

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.

A closing auction lines up piles sealed bins on a shelf, left to right. Bin i contains piles[i] tokens.

Iris claims a bin first, then Odell, and they keep alternating. A claim always takes one whole bin from either the far left or the far right of whatever is still on the shelf, and every token inside a claimed bin is credited to whoever claimed it. The duel ends when the shelf is bare, and by then every bin has been claimed.

Each of them plays for the largest personal token total they can force, whatever the other one does.

Return true if Iris finishes with a strictly larger token total than Odell, and false otherwise.

Examples

Example 1

Input: piles = [3, 9, 1, 2]
Output: true

Iris ends the duel with a strictly larger token total than Odell, so true is returned.

Example 2

Input: piles = [1, 2]
Output: true

Iris claims the right-hand bin for 2 tokens, Odell is left with the bin holding 1, and 2 beats 1.

Example 3

Input: piles = [5, 4, 3, 1]
Output: true

Iris finishes ahead of Odell over the four claims.

Example 4

Input: piles = [2, 7, 4, 8, 9, 1]
Output: true

Iris finishes with a larger total than Odell across the six claims, so true is returned.

Constraints

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles[i]) is odd.

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 first_bidder_wins(bins: list[int]) -> bool:

Java

public boolean firstBidderWins(int[] bins)

The intended approach

Time O(n^2)Space O(n)

For every contiguous span of the shelf, record how far ahead the bidder who moves first on that span can end up. A span is settled from the two spans one bin shorter: claiming the left bin scores that bin minus whatever the other bidder then leads by on the rest, and likewise for the right bin. Spans are filled in increasing length with a single row that is overwritten in place, and the answer is whether the lead over the whole shelf is positive.

Pythonentry point: first_bidder_wins

def first_bidder_wins(bins):
    # Interval table on the lead the mover holds over the other bidder. One
    # rolling row is enough because a span of length L only reads spans of
    # length L-1 that start at the same index or one further right.
    # Time O(n^2). Space O(n).
    n = len(bins)
    lead = list(bins)
    for span in range(2, n + 1):
        for i in range(0, n - span + 1):
            j = i + span - 1
            take_left = bins[i] - lead[i + 1]
            take_right = bins[j] - lead[i]
            lead[i] = take_left if take_left > take_right else take_right
    return lead[0] > 0

The obvious version

Plain recursion over the two ends of the remaining span with no table, recomputing every span as often as it comes up.

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_first_bidder_wins(bins):
    n = len(bins)

    def lead(i, j):
        if i == j:
            return bins[i]
        return max(bins[i] - lead(i + 1, j), bins[j] - lead(i, j - 1))

    return lead(0, n - 1) > 0

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
4 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