0301MediumArrayMathDynamic ProgrammingRecursionMinimaxGame TheoryZero-Sum Game

Bundle Claim 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.

Two auditors clear a row of document bundles. bundles[i] is the page count of the bundle at position i, and page counts are never negative.

The first auditor moves first and the two then alternate. A move takes the bundle at either end of the row that is left, adds its page count to that auditor's tally, and shortens the row. Play continues until no bundle remains. Both auditors know the whole row from the start and both play as well as possible for their own final tally.

Return true if the first auditor's final tally is at least as large as the second auditor's, and false otherwise. An equal pair of tallies counts in the first auditor's favour.

Examples

Example 1

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

With both auditors playing as well as they can, the first ends on 11 pages and the second on 4, so the first is not behind.

Example 2

Input: bundles = [4,8,3]
Output: false

Best play from both sides ends with the first auditor on 7 pages and the second on 8.

Constraints

1 <= bundles.length <= 20
0 <= bundles[i] <= 10^7

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

Java

public boolean firstAuditorWins(int[] bundles)

The intended approach

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

Score a stretch of the row by the best tally advantage its mover can secure, which is the bundle taken minus the advantage the opponent then secures on what is left. Build these figures for stretches of growing length in one rolling row, and answer on the sign of the figure for the whole row.

Pythonentry point: first_auditor_wins

def first_auditor_wins(bundles):
    # lead[i] is the largest tally advantage the auditor about to move can secure on
    # the stretch that starts at i, for the stretch length currently being built.
    # Lengths grow one at a time and the row is rewritten left to right, so the two
    # shorter stretches a move leads to are both still readable when needed.
    # O(n^2) time, O(n) space.
    n = len(bundles)
    lead = list(bundles)
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            from_left = bundles[i] - lead[i + 1]
            from_right = bundles[j] - lead[i]
            lead[i] = from_left if from_left > from_right else from_right
    return lead[0] >= 0

The obvious version

Recurse over the open stretch of the row, trying both ends at every move and returning the better advantage, with no table kept between calls.

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_auditor_wins(bundles):
    n = len(bundles)

    def advantage(i, j):
        if i == j:
            return bundles[i]
        left = bundles[i] - advantage(i + 1, j)
        right = bundles[j] - advantage(i, j - 1)
        return left if left > right else right

    return advantage(0, n - 1) >= 0

How this problem was checked

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