CF 1930A - Maximise The Score

CF 1930A - Maximise The Score

Rating: 800
Tags: greedy, sortings
Solve time: 1m 32s
Verified: yes

Solution

Problem Understanding

We are given a list of 2n positive integers, and we need to perform exactly n moves. Each move consists of picking two numbers from the list, adding the smaller of the two to our score, and removing both numbers from the list. Our task is to maximize the total score after all moves are done. The output for each test case is a single integer representing this maximum achievable score.

The constraints are moderate: n can be up to 50, which means the list has at most 100 elements. Since the numbers themselves can be as large as $10^7$, we need to be mindful of arithmetic, but Python handles integers comfortably here. The time limit is 1 second, and there can be up to 5000 test cases. This means each test case must run extremely fast, preferably in linearithmic time with respect to the number of elements, and certainly not quadratic.

A subtle edge case occurs when all numbers are equal, for example 2 2 2 2. Any naive pairing that ignores order might accidentally assume different outcomes, but the maximum score here is simply the sum of the smaller elements from each pair, which are all identical. Another edge case is when the largest numbers are paired with the smallest numbers. Careless greedy choices, like always pairing the two largest, can lead to suboptimal scores. For instance, [1, 2, 3, 100] yields a higher score if we pair 1 with 2 and 3 with 100 rather than 100 with 3 and 2 with 1.

Approaches

The brute-force approach would try all possible pairings of the numbers, calculate the resulting score for each sequence of moves, and select the maximum. With 2n elements, the number of ways to pair them is $(2n-1) \cdot (2n-3) \cdot ... \cdot 1$, which grows super-exponentially. Even for n=10, this is already infeasible.

The key observation is that in each move we only add the minimum of the pair to the score. This means that to maximize our score, we should make sure the smaller numbers are not wasted by pairing them with extremely large numbers. In other words, if we sort the array and pair the numbers consecutively, the smaller number in each pair is as large as possible given the remaining numbers. Sorting ensures that every move contributes the highest possible min(x, y) at that stage. This reduces the problem to sorting the array and summing every other number starting from the smallest.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O((2n)!)	O(n)	Too slow
Optimal	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

1. Read the number of test cases t.
2. For each test case, read the integer n and the list of 2n numbers.
3. Sort the list of numbers in non-decreasing order. Sorting organizes numbers so that small numbers are paired together and contribute fully to the score.
4. Initialize a variable score to zero. This will accumulate the sum of the minimums.
5. Iterate through the sorted list, adding every second number (indices 0, 2, 4, ..., 2n-2) to score. These are the smaller elements in each consecutive pair.
6. Print the score for each test case.

Why it works: Sorting guarantees that every pair we form consists of two consecutive numbers. In such a pair, the smaller number is always one of the largest possible choices among remaining numbers, so the sum of all these minimums is maximized. Any other pairing would either decrease the minimum in a pair or waste a larger number by pairing it with a much smaller number.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    score = sum(a[i] for i in range(0, 2*n, 2))
    print(score)

The solution reads input efficiently using sys.stdin.readline to handle multiple test cases quickly. Sorting is crucial, as it ensures the smallest numbers are paired optimally. Using a step of 2 in the range when summing ensures we pick exactly the smaller element from each consecutive pair. Forgetting this step size would produce an incorrect score. Python handles integers without overflow, so no special care is needed for large values.

Worked Examples

Trace for input 1 2 3 100 with n=2:

Step	Sorted Array	Pairs	Score
Initial	[1, 2, 3, 100]	-	0
Pair 1	[1, 2]	min=1	1
Pair 2	[3, 100]	min=3	4

The trace shows the smaller numbers are paired to maximize contribution. Pairing 100 with 1 would give only 1 + 2 = 3, which is worse.

Trace for input [1, 1, 1, 1, 1, 1] with n=3:

Step	Sorted Array	Pairs	Score
Initial	[1, 1, 1, 1, 1, 1]	-	0
Pair 1	[1, 1]	1	1
Pair 2	[1, 1]	1	2
Pair 3	[1, 1]	1	3

This confirms that when all numbers are equal, the algorithm still produces the correct sum.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(t * n log n)	Sorting each list of size 2n dominates, iteration to sum is O(n)
Space	O(2n)	Storing the array for each test case

Given n <= 50 and t <= 5000, the algorithm performs at most 5000 * 100 * log 100 ≈ 500,000 operations, which fits comfortably within the 1-second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    # solution
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        a.sort()
        score = sum(a[i] for i in range(0, 2*n, 2))
        print(score)
    return output.getvalue().strip()

# provided samples
assert run("3\n1\n2 3\n2\n1 1 2 1\n3\n1 1 1 1 1 1\n") == "2\n2\n3", "sample 1"

# custom cases
assert run("1\n1\n100 1\n") == "1", "small numbers edge"
assert run("1\n2\n5 5 5 5\n") == "10", "all equal numbers"
assert run("1\n3\n1 2 3 4 5 6\n") == "9", "consecutive numbers"
assert run("1\n4\n1 100 2 99 3 98 4 97\n") == "10", "mix small and large numbers"
assert run("1\n50\n" + " ".join(str(i) for i in range(1, 101)) + "\n") == "1275", "max n"

Test input	Expected output	What it validates
1 100 1	1	smallest array, pairing smallest with largest
5 5 5 5	10	all equal numbers produce predictable sum
1 2 3 4 5 6	9	consecutive numbers maximize sum of minimums
1 100 2 99 3 98 4 97	10	pairing strategy with extreme values
n=50, numbers 1-100	1275	stress test for maximum input size

Edge Cases

When all numbers are equal, for example n=3 and [2, 2, 2, 2, 2, 2], sorting preserves the array. The algorithm pairs [2,2],[2,2],[2,2], giving a sum of 6. The output is correct and independent of the original order.

When there is a large number paired with a small number, like [1, 2, 3, 100], sorting ensures that 1 is paired with 2 and 3 with 100, maximizing the sum of minimums to 4. Any alternative pairing would reduce the total score, confirming the algorithm handles the case optimally.