Tug-of-war ladder

The village fete runs its tug-of-war as a ladder: the two strongest teams pull against each other first, and whatever survives goes back in the draw.

The problem

Every team on the field has a pull rating, a whole number of points. The steward runs the ladder one round at a time, and each round works like this. Take the two teams with the highest ratings. If their ratings differ, the stronger team wins; the weaker team leaves the field, and the winner is left exhausted, its rating reduced by exactly the loser's rating. If the two ratings are equal, the pull ends in a stalemate and both teams leave the field. A team whose rating drops to zero is finished and leaves too.

The steward repeats this until fewer than two teams remain. Report the rating of the team still standing, or 0 if the field has emptied.

Input. ratings — a list of integers, the pull rating of each team.

Output. The rating of the last team on the field, or 0 if none is left.

Example.

ratings = [5, 12, 9, 3, 12]  ->  1

The two twelves stalemate and both leave, leaving [5, 9, 3]. Then 9 beats 5 and becomes 4, leaving [4, 3]. Then 4 beats 3 and becomes 1. One team, rating 1.

A second example, where the field empties:

ratings = [10, 4, 4, 2]  ->  0

10 beats 4 and becomes 6; 6 beats 4 and becomes 2; the two twos stalemate. Nobody is left, so the answer is 0.

Constraints.

• 0 <= len(ratings) <= 10^5
• 1 <= ratings[i] <= 10^4

Hints

Approach

Brute force

Scan for the largest rating, scan again for the second, remove both, append the difference, repeat. Each round costs O(n) and there are up to n rounds — about 10¹⁰ comparisons at the top of the range.

The insight

Every round asks the same question — what are the two largest values right now — and the value it produces is smaller than both, so it can be dropped back into the same structure without disturbing anything else.

That is the exact contract of a heap: extract-max and insert, each in O(log n), with no requirement that the rest ever be fully sorted. Because the difference of two ratings is strictly smaller than the larger of them, the total of all ratings falls every round, so the process always ends.

Algorithm

1. Negate every rating and heapify, giving a max-heap.
2. While at least two teams remain, pop the two largest ratings a and b.
3. If a != b, push a - b back onto the heap.
4. When one or zero teams remain, return the survivor's rating or 0.

Complexity

Time O(n log n) — the initial heapify is O(n), and each of at most n rounds does a constant number of O(log n) heap operations. Space O(n) for the heap.

Solution

"""Tug-of-war ladder — repeated extract-max on a heap, the difference pushed back."""

import heapq


def solve(ratings):
    # heapq is a min-heap, so negated ratings put the strongest team at the front.
    field = [-r for r in ratings]
    heapq.heapify(field)

    # Invariant: the field holds every team still able to pull, and each round
    # strictly lowers the sum of the ratings, so the loop terminates.
    while len(field) > 1:
        strongest = -heapq.heappop(field)
        runner_up = -heapq.heappop(field)
        if strongest != runner_up:               # a stalemate retires both teams
            heapq.heappush(field, -(strongest - runner_up))

    return -field[0] if field else 0

TESTS = [
    (([5, 12, 9, 3, 12],), 1),
    (([10, 4, 4, 2],), 0),
    (([4, 9, 2, 2],), 1),
    (([6, 6],), 0),
    (([14],), 14),
    (([],), 0),
    (([7, 7, 7, 7],), 0),
    (([10000, 1],), 9999),
]

Pitfalls

• Pushing the difference back without negating it. The heap holds negated ratings, so a raw a - b sorts as though it were the strongest team on the field and the first example returns -7 instead of 1.
• Looping on while field: rather than while len(field) > 1. The second pop raises IndexError the moment one team is left, so [14] crashes where it should answer 14.
• Forgetting the negation on the way out. Ratings live in the heap as negatives, so field[0] gives -1 where the answer is 1 — and an empty field has no field[0] at all, which is the [] case answering 0.

Variants

• Screen-print rotation — the same extract-max loop, but items come back after a fixed delay rather than immediately.
• Back-to-back on air — extract two at a time again, this time to keep equal items apart.