Game on Array

Let $cnt[x]$ be the number of elements currently equal to $x$. A move on $x$ gives $cnt[x]$ points, then moves that whole bucket to $x-1$.

The important part is not the actual values as much as their parity.

All-even states are fair

Suppose every positive value in the array is even, and some player chooses an even value $x$ with bucket size $c$.

After the move, those $c$ elements become $x-1$, which is odd. Since the state had no odd values before, the opponent can choose $x-1$ immediately and also score exactly $c$.

Then those elements become $x-2$, which is even again. So after two moves:

• both players gained the same number of points,
• the array is all-even again.

Repeat this forever. So from an all-even state, the rest of the game gives equal points to both players, no matter whose turn it is.

That means all even layers are basically accounting noise. They split evenly.

Odd buckets are the only bonuses

Now look at an odd value $x$ with frequency $c$.

If a player chooses this bucket, they get $c$ points and the bucket moves to $x-1$, which is even. After that, this bucket belongs to the fair all-even machinery unless it interacts with other choices later. The key is: the unpaired bonus from this odd bucket has been claimed.

So every initially odd value contributes one prize equal to its frequency.

For example, if the odd values have frequencies $5, 2, 2$, then those are the only contested bonus chunks. Everything else is split evenly like a tax form, sadly but cleanly.

Why not choose an even value first?

This is the tempting false move.

Say a player chooses an even value $2k$ with bucket size $e$. It moves to odd value $2k-1$.

If there was already an odd bucket there with size $o$, the opponent can now choose $2k-1$ and score $e+o$. The $e$ cancels the first player’s $e$, and the opponent also gets the odd bonus $o$. So the first player just handed over value. Nice job, genius.

If there was no odd bucket there, the opponent can still choose $2k-1$ and score $e$, making the pair neutral. That does not improve anything; it just burns two moves and returns to the same kind of decision.

So optimal play can be described as: while odd buckets exist, players choose odd buckets.

The reduced game

Now the game is simple:

• each distinct odd value gives one prize equal to its frequency,
• choosing that prize removes it,
• players alternate turns,
• both want maximum total score.

For independent positive prizes, optimal play is just picking the largest remaining prize each turn. If Alice skips the largest one, Bob takes it. No galaxy-brain nonsense needed.

So:

1. Count frequencies of odd values in the original array.
2. Sort these frequencies in descending order: $b_0, b_1, \dots$.
3. Alice gets $b_0 + b_2 + b_4 + \dots$ as bonus advantage chunks.
4. Bob gets $b_1 + b_3 + b_5 + \dots$.

Let

$diff = b_0 - b_1 + b_2 - b_3 + \dots$

This is Alice’s final score minus Bob’s final score.

Let

$S = \sum a_i$

be the total number of points awarded in the whole game. Then:

$Alice = \frac{S + diff}{2}$

$Bob = \frac{S - diff}{2}$

The parity works out because both $S$ and $diff$ have the same parity: even-valued elements do not affect parity, and each odd element contributes once to the odd-frequency total.

Complexity is $O(n \log n)$ per test case from sorting the odd frequencies, with total $n \le 2 \cdot 10^5$. Easy fit.