Editorial for An Animal Contest 2 P4 - Koala Gambling


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: WilliamWu277

We split this problem into two cases:

Odd N: We arrange the array in non-decreasing order. For example, let the array be a, b, c, d, e such that a \le b \le c \le d \le e. It is easy to see that if Ken picks e, it is always optimal for his opponent to pick d, the next largest available number. If his opponent picks a, he leaves the current largest number in the line, d, available to Ken. Ken then picks c, causing his opponent to pick b. Finally, Ken picks a. Since Ken's total after the first \frac{N-1}{2} moves is always greater or equal to his opponent's, the selection of the N^\text{th} or smallest element guarantees him the win.

Even N: We first realize the only case where the answer is -1 is when all elements in the array are the same.

We start by sorting the array in non-decreasing order. Let us call the first half of the array (the larger half) b and the second half (the smaller half) c. We arrange a in the following manner: b_i, c_i, b_j, c_j, \dots, b_z, c_z.

To understand why, consider that on each of Ken's turns, he picks an element from b. Then, his opponent is always left with an element from c. This process repeats until Ken selects the entire array b and his opponent selects the entire array c. Since all elements in b are greater than or equal to all elements in c and the array consists of more than one distinct number, the sum of elements in b must be strictly greater than the sum of elements in c, as desired.

Time Complexity: \mathcal{O}(T \cdot N \log N)


Comments

There are no comments at the moment.