Two crews, one siding

Two crews clear one siding from the head, turn about. A bigger pull now raises the cap on the other crew's next pull, so grabbing loses.

The problem

A line of wagons stands at the head of a siding in a fixed order; nobody may reach past the front. Two crews empty it, the early crew first, alternating until the line is gone.

The yard agreement sets the size of a pull. The reach starts at 1 and always equals the largest single pull either crew has made. On its turn a crew takes the next x wagons off the head, where 1 <= x <= 2 * reach and x is at most the number still standing; afterwards reach becomes max(reach, x).

Both crews are paid by tonnage, both see the whole line, and both know the other plays just as hard. Report what the early crew ends the shift with.

Input. wagons — the tonnage of each wagon, head of the line first.

Output. The early crew's tonnage when both crews play to maximise their own.

Example.

wagons = [4, 9, 3, 7]   ->  13

The early crew takes the first two, 4 + 9; the late crew clears 3 + 7. Taking only the 4 keeps reach at 1, but the late crew answers with 9 and 3, leaving the early crew the single 7, for 11.

A second example, where going first is no advantage:

wagons = [2, 8, 1, 9, 4, 3]   ->  12

The line is worth 27, so the early crew ends under half of it. Taking the first two banks 10, but reach becomes 2 and the late crew sweeps the rest, 17. Taking the single 2 holds the 9 out of range.

Constraints.

• 1 <= len(wagons) <= 100
• 1 <= wagons[i] <= 10^4

Hints

Approach

Brute force

Play out every legal sequence of pulls. Each turn offers up to 2 * reach choices, so the tree branches like the ways of cutting the line up — past twenty wagons, more than 10⁹ leaves.

The insight

The two crews split the whole tail between them, so one function serves both: the crew on duty wins remaining[i] minus whatever the other crew wins from the position it inherits.

The game is zero-sum over a fixed pot — every wagon from i on goes to one crew or the other — so maximising your own tonnage is minimising theirs, and one on_duty(i, reach) serves whoever stands there. That pair is the whole state: pulled wagons are gone, and reach is the only trace the past leaves.

Algorithm

1. Build remaining[i], the tonnage from wagon i to the tail, backward.
2. Define on_duty(i, reach): the best total for the crew on duty.
3. If i + 2 * reach >= n, it takes the lot — return remaining[i].
4. Otherwise score each x in 1..2 * reach as remaining[i] - on_duty(i + x, max(reach, x)) and keep the best.
5. Memoise on (i, reach). The answer is on_duty(0, 1).

Complexity

Time O(n³) — n positions times n values of reach, each trying up to 2n pulls; at n = 100, under a million steps. Space O(n²) for the memo.

Solution

"""Two crews, one siding — game DP over the suffix, keyed on (position, reach)."""

from functools import lru_cache


def solve(wagons):
    n = len(wagons)
    if n == 0:
        return 0

    # remaining[i] = tonnage still on the siding from wagon i to the end
    remaining = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        remaining[i] = remaining[i + 1] + wagons[i]

    @lru_cache(maxsize=None)
    def on_duty(i, reach):
        """Most tonnage the crew whose turn it is can end with, from wagon i on."""
        # invariant: the two crews split remaining[i] between them, so whatever
        # the other crew wins from the rest is exactly what this crew gives up
        if i + 2 * reach >= n:
            return remaining[i]          # the whole tail is reachable in one pull
        return max(
            remaining[i] - on_duty(i + x, max(reach, x))
            for x in range(1, 2 * reach + 1)
        )

    answer = on_duty(0, 1)
    on_duty.cache_clear()                # the cache belongs to this call only
    return answer

TESTS = [
    (([4, 9, 3, 7],), 13),
    (([2, 8, 1, 9, 4, 3],), 12),
    (([6, 6, 6, 6, 6],), 18),
    (([12],), 12),
    (([5, 1],), 6),
    (([3, 3, 9, 1, 4, 7, 2],), 17),
    (([1, 1, 1, 1, 1, 1, 1],), 4),
    (([7, 6, 8, 12, 1, 8, 1, 5, 12],), 31),
]

Pitfalls

• Reporting the margin, not the total. The subtraction yields a tonnage only because remaining[i] is the whole pot. Memoise "how far ahead the crew on duty is" and [4, 9, 3, 7] returns 3, the gap between 13 and 10.
• Setting reach = x instead of max(reach, x). A one-wagon pull then shrinks the cap back: [7, 6, 8, 12, 1, 8, 1, 5, 12] reports 37 where the answer is 31, a total no legal play produces.
• Letting x run off the end of the line. Bounded only by 2 * reach, i + x overshoots remaining: an index error, or credit for an impossible pull. Test i + 2 * reach >= n first.

Variants

• Linear DP — where one-index recurrences come from; this one adds an index because the cap travels with the position.
• The jackpot sign — a table read back after filling, with an exact budget in place of an opponent.