1082. Pairing to Keep the Largest Sum Down
m numbers are given, with m even. Split them into m / 2 pairs, using
every number exactly once. The COST of a pairing is the largest sum of any single pair.
Print the smallest cost achievable.
3 5 2 3 -> 7 pairs (2,5) and (3,3)
3 5 4 2 4 6 -> 8 pairs (2,6), (3,5), (4,4)
1 2 3 4 -> 5 pairs (1,4) and (2,3)
10 1 1 1 -> 11
## What most people try first
Try every pairing. The number of ways to pair m items is
(m-1) * (m-3) * ... * 1, which is 945 at m = 10 and impossible by m = 30. That is
the brute force this problem was checked against for m <= 8.
The instinct to pair EQUAL values together, or to pair neighbours in sorted order, is wrong:
on 1 2 3 4 pairing neighbours gives pairs (1,2) and (3,4) with cost 7, and the
answer is 5.
## Sort, then pair the ends inwards
sort ascending
answer = max over i in 0 .. m/2 - 1 of (a[i] + a[m-1-i])
So the smallest goes with the largest, the second smallest with the second largest, and so on.
## Why the largest must meet the smallest
Take any optimal pairing and look at the largest number a[m-1]. Suppose it is paired with
some x, while the smallest number a[0] is paired with some y. Repair the pairing by
putting a[m-1] with a[0] and x with y. The two new sums are
a[m-1] + a[0] <= a[m-1] + x because a[0] <= x
x + y <= x + a[m-1] because y <= a[m-1]
so BOTH new sums are at most the old sum a[m-1] + x, which was already one of the pairs
being maximised over. The largest pair sum therefore cannot rise.
Remove those two and repeat on the remaining m - 2 numbers. Peeling the extremes off one
pair at a time turns any optimal pairing into the sorted-ends one without ever increasing the
cost.
## Where this sits
Problem #610 also sorts and walks in from both ends, but it asks how many BOATS are needed under a fixed weight limit, so its sweep advances one pointer conditionally and the other always. Here the number of pairs is fixed and the limit is the unknown, which is why every pair is formed unconditionally and the answer is a maximum rather than a count.
Problem #1084 is the deliberate companion: same pairing question, but it maximises the total of the pair MINIMUMS, and its answer pairs NEIGHBOURS rather than ends. Solving both and being able to say why the two rules differ is the exercise.
## Overflow
Two numbers of 10^9 sum to 2 * 10^9. That is LESS than the signed 32 bit limit of
2147483647, so the pair sums fit in 32 bits, narrowly. Nothing here overflows, and a test
sitting at exactly 2 * 10^9 is included so the claim is checkable rather than assumed.
## Cost
Time O(m log m). Space O(m).
Constraints - `2 ≤ m ≤ 200000` and `m` is even - `0 ≤ a[i] ≤ 1000000000`
Input
The first line contains an even integer m.
The second line contains m space-separated integers.
Output
Print one integer alone on a line: the smallest possible value of the largest pair sum. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.