Absolute Game#12807

Absolute Game (Editorial)

Author:

Roman Bilyi

Developer:

Roman Bilyi

Editorialist:

Stanislav Bezkorovainyi

Claim. This game is equivalent to the game where Alice has to choose from her array and then Bob has to choose from his array.

Proof. Since Alice can finish the game with whatever she wants, the result of the game for Bob can't be better than in the game mentioned above. Now let's prove that it is always possible for Bob to achieve this.

At first, let's define an array of elements. Each c_i has such value, that the value of |a_i - b_{c_i}| is minimal possible. If for some position there are more than one possible c_i, then choose the smallest one. In other words, we build an array such that if Alice finishes the game with x = a_i, then the best outcome for Bob is if y = b_{c_i}.

Let's say that in the first turn, Alice removes some element a_i. Then we should also remove the element c_i from array . Now, since there are n-1 elements of the array , there is at least one such position 1 \le p \le n, that c_i \neq p for every . Bob should remove the element b_p. It is optimal because whatever we end up with, he will still be able to choose the best possible from the remaining elements of array .

In general, if after some turns there are elements in Alice's array and Bob's array, now it's Alice's turn and if she removes an element a_i from her array, then Bob should remove an element b_p on such position that there are no c_i = p among all possible (i.e. among all such that a_i have not been removed yet).

If Bob plays the way mentioned above, then after each his turn, for every from the remaining array , he will be able to choose the best possible from the remaining array .

Ok, I got it. But how to implement it? Implementation of the "light version" of the game is rather straightforward. Let's define an array such that ans_i is the answer if Alice decides to choose to be equal to a_i. If is equal to a_i, then Bob will obviously choose such that |x-y| is minimal possible. Thus, we get the formula:

ans_i = \min_{j=1}^n{|a_i-b_j|}

Since Alice wants to maximize |x-y|, the final answer is equal to \max_{i=1}^n{ans_i}.