1073. The Middle Coin of Every Three

n piles of coins are given, where n is a multiple of 3. The piles are shared out in rounds. In each round, three piles that are still unclaimed are chosen, and the largest of the three goes to Alice, the second largest to YOU, and the smallest to Bob. Rounds continue until nothing is left.

You choose which three piles go into each round. Print the largest total you can end up with.

2 4 1 2 7 8 -> 9 rounds (8,7,1) and (4,2,2): you get 7 and 2 2 4 5 -> 4 1 2 3 4 5 6 -> 8 rounds (6,5,1) and (4,3,2): you get 5 and 3

Ties among equal piles are broken any way you like; it does not change the total.

## What most people try first

Search over groupings. The number of ways to split 3g piles into g unordered triples is enormous even for g = 4, and it is the brute force this problem was checked against for n <= 9.

The obvious greedy is also wrong: "take the largest three piles first" gives you the SECOND largest pile and then burns the largest and the third largest, which is the same as the right answer for one round and wrong about what to sacrifice.

## The rule

Sort descending. Then, writing a[0] >= a[1] >= ... >= a[n-1],

answer = a[1] + a[3] + a[5] + ... + a[2g-1] where g = n / 3

so you take every second pile from the top, g of them, and the bottom third of the list is written off entirely.

On 1 2 3 4 5 6 sorted descending as 6 5 4 3 2 1, that is a[1] + a[3] = 5 + 3 = 8.

## Why you cannot do better

Look at the piles you receive, sorted descending, and call the jth of them x_j. Each round you receive one pile and Alice receives a strictly larger or equal one from the SAME round. So the j rounds that produced x_1 .. x_j also produced j piles for Alice, each at least as large as the pile you got in that round, hence at least x_j.

That gives j of Alice's piles plus your own j, so at least 2j piles are at least x_j, meaning x_j <= a[2j-1] in the sorted list. Summing over j = 1 .. g:

your total <= a[1] + a[3] + ... + a[2g-1]

## Why that bound is reached

Use the rounds

round i, for i = 0 .. g-1: piles a[2i], a[2i+1], a[2g+i]

Every index from 0 to 3g-1 is used exactly once. Within round i, sorting gives a[2i] >= a[2i+1] >= a[2g+i], the last because 2i+1 <= 2g-1 < 2g <= 2g+i and the list descends. So Alice takes a[2i], you take a[2i+1], and Bob takes a[2g+i].

Bound met, so the formula is exactly the answer.

## What the argument really says

The bottom third of the piles is worthless to you and must be spent, one per round, on Bob. Having accepted that, the top two thirds pair off and you get the lower of each pair. Seeing which part of the input is DEAD, before optimising over the rest, is the move to take away.

## The indices

a[1], a[3], ..., a[2g-1], which is g terms, not n / 2 terms. Running the sum over all odd indices takes a[2g+1] and beyond as well, which belongs to Bob. A row of 12 piles answers with 4 terms, not 6, and that case is in the tests.

## Overflow

n reaches 99999 and a pile reaches 10^9, so the total reaches roughly 3.3 * 10^13. The signed 32 bit limit is 2147483647, so the accumulator must be 64 bit, and nine piles of 10^9 already total 3 * 10^9.

## Cost

Time O(n log n). Space O(n).

Constraints - `3 ≤ n ≤ 99999` and `n` is a multiple of 3 - `0 ≤ pile[i] ≤ 1000000000`