0444EasyArrayGreedySortingCounting Sort

Doubles for the Club Regatta

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 rowing club is drawing up doubles for a regatta. margins carries one entry per member: the number of seconds by which that member beats the club standard over the course, so a member who is slower than the standard has a negative entry. The club has an even number of members and every one of them has to be placed in exactly one double.

A double is credited with the lesser of its two members' margins, since a crew can only go as fast as its slower half. The club's score for a set of doubles is the total credited across all of them.

Return the highest score the club can reach, over every way of splitting the members into doubles.

Examples

Example 1

Input: margins = [5, 5, 1, 9]
Output: 6

Rowing the doubles as (1, 5) and (5, 9) records margins of 1 and 5.

Example 2

Input: margins = [-4, -9, -2, -7]
Output: -13

Rowing (-9, -7) as one double and (-4, -2) as the other records -9 and -4.

Example 3

Input: margins = [12, -30, 7, 12, -30, 40]
Output: -11

The doubles (-30, -30), (7, 12) and (12, 40) record -30, 7 and 12.

Example 4

Input: margins = [0, -10000]
Output: -10000

Two members make up the only double, and the crew is held to the slower of them.

Constraints

margins.length == 2 * n
1 <= n <= 10^4
-10^4 <= margins[i] <= 10^4

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 best_pair_total(margins: list[int]) -> int:

Java

public int bestPairTotal(int[] margins)

The intended approach

Time O(n log n), dominated by ordering the members.Space O(n) for the ordered copy of the margins.

Put the members in order of margin. The slowest member is credited whoever they row with, so the least is lost by giving them the next member along; peel that couple off and the same reasoning applies to what is left, which leaves the ordered list cut into neighbouring couples. Adding up every other entry from the front of the ordered list gives the score.

Pythonentry point: best_pair_total

def best_pair_total(margins):
    # Order the members by margin. Once ordered, the slowest member has to sit in
    # some double, and whatever is paired with them is wasted, so the cheapest
    # thing to waste is the next member along; repeating that argument leaves the
    # ordered list split into neighbouring couples, and the score is the total of
    # the first member of each couple.
    # O(n log n) time for the ordering, O(n) space for the ordered copy.
    ordered = sorted(margins)
    score = 0
    for at in range(0, len(ordered), 2):
        score += ordered[at]
    return score

The obvious version

Try every way of matching the members up: fix the first member left in the pool, pair them with each other member in turn, credit the lesser margin, and recurse on the members that remain, keeping the best total.

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_best_pair_total(margins):
    pool = list(margins)

    def best(left):
        if not left:
            return 0
        first = left[0]
        top = None
        for other in range(1, len(left)):
            partner = left[other]
            rest = left[1:other] + left[other + 1:]
            score = (first if first < partner else partner) + best(rest)
            if top is None or score > top:
                top = score
        return top

    return best(pool)

How this problem was checked

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