4
1 2 3 4

The idea is interesting, but this is also incorrect: in the odd case, sticking to pairs may not be the best strategy of A: to mix pairs but exclude the worst one may yield smaller answer.

Counterexample is this:

7
1 2 3 4 50 125 140

Answer is 3, not 15. (A has 3 turns, and he excludes 50, 125, 140)

Were all the solutions of participants incorrect, too?

What is wrong with while(hi-lo > 1e-9), exactly? I used long double there.

Oh, thank you! But... What is going on?! You've changed only the sizes of arrays, but they were large enough in both submissions.

Why is this 13576829 submission fails? I use 64-bit type here, so no overflow should occur. But is does...

There is an another pair (2,2). We don't have a restriction l + s ≤ n

Problem H could be solved in O(1) without any binary search. Consider the case when a, b, c, d ≥ 0. Then define . One may note,

Take B as the above matrix. Then the answer in this case equals |x|. (But we strictly proved only that answer $\leq x$ ).

If some of a, b, c, d are negative, this also holds, but better answer exist. We wanna get |a| + |b| + |c| + |d| in the denominator of x. One may note that if we have an even number of negative elements, it is possible to use the same B matrix, but reverse somewhere signs for x'es (and get , and |x| as an answer). For example, if a < 0 and c < 0, we take

Only essential case is if we have an odd number of negative elements in initial matrix. Then we have to subtract minimal element of (|a|, |b|, |c|, |d|) instead of adding, and answer equals

However, I was unable to prove the minimality of x chosen this way during the contest (but solution got AC). Any ideas?