Editorial: Arithmetic Game

$n$ — size of array $a$

$a$ — array of numbers

This is a minimax game: Alice wants to minimize the final score, Bob wants to maximize it. Both play optimally, and Alice moves first.

Recall that the arithmetic mean uses floor division: $\lfloor S / n \rfloor$.

Subtask 1: $n = 3$ ($20$ points)

With only $3$ elements, Alice removes one and Bob removes another, leaving a single element as the final score. There are only $3$ choices for Alice and $2$ remaining choices for Bob — we can check all $6$ possibilities with conditional statements.

Time complexity: $O(1)$
Space complexity: $O(1)$

Subtask 2: All $a_i$ are the same ($15$ points)

If all values are equal to some constant $c$, then the arithmetic mean is $\lfloor nc / n \rfloor = c$ before removal and $\lfloor (n-2)c / (n-2) \rfloor = c$ after removal. The score never changes, so the answer is always .

Time complexity: $O(n)$
Space complexity: $O(n)$

Subtask 3: $n \leq 10^3$ ($25$ points)

We brute-force the minimax. For each possible choice $a_i$ that Alice can remove, we simulate Bob's optimal response: Bob will pick the element $a_j$ ($j \neq i$) that maximizes the final score . This means Bob will remove the smallest remaining element (since removing a smaller value keeps the sum larger).

For each Alice choice $a_i$, we compute the best Bob can achieve. Alice will choose the $a_i$ that minimizes this value. We then compare the result to the initial score.

Time complexity: $O(n^2)$
Space complexity: $O(n)$

Subtask 4: Full Solution ($40$ points)

Alice wants to reduce the final score as much as possible, so her optimal strategy is to remove the largest element — this reduces the sum maximally. Bob wants to keep the final score as high as possible, so his optimal strategy is to remove the smallest remaining element — this preserves the sum as much as possible.

Algorithm:

1. Sort the array $a$.
2. Compute the initial score: $\text{initial} = \lfloor S / n \rfloor$ where $S = \sum a_i$.
3. Remove $a[n-$ (largest, Alice's choice) and (smallest, Bob's choice).

Time complexity: $O(n)$
Space complexity: $O(n)$

Solution Code