MEXGAME1 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game on an array, taking turns repeatedly reducing elements by 1 as long as the MEX of the array doesn’t change.
Under optimal play, who wins?

EXPLANATION:

Let M = \text{MEX}(A).
We know that the array must contain (at least) one copy of every value smaller than M.

In order for M to remain the MEX of the array, a move must:

  • not create a new copy of M (i.e. do M+1 \to M), and
  • not remove the last copy of any value smaller than M.

We’ll analyze values smaller than M and larger than M separately.

First, consider a value x \gt M.
A player (doesn’t matter who) can repeatedly subtract 1 from this value till it reaches M+1; at which point neither player will touch it again unless they’re forced to.
Thus, x - (M+1) subtractions will be performed on this element in total since it will surely reach M+1 before a loser is decided.

Next, consider a value x \lt M.
Suppose there f_x occurrences of x.
Then, f_x-1 of these occurrences may be freely reduced to 0 via subtractions, while the last one won’t be touched.
This gives a total of (f_x-1)\cdot x operations possible; and all of these operations will always be available no matter what the players do (to see why, look at the number of moves that are M-1 \to M-2, then the number of moves that are M-2 \to M-3, and so on in decreasing order.)

Observe that in both cases, the number of moves available was totally independent of the actual moves made!
Thus, the winner of the game depends purely on the number of moves available: if this count is odd Alice wins, otherwise Bob wins.

Counting the number of moves is simple, since we saw:

  • Every value x\gt M adds x-(M+1) to the count for each of its appearances, for f_x \cdot (x-M-1) in total.
  • Every value x \lt M adds (f_x-1) \cdot x to the count.

Sum this up across all x and then check its parity to obtain the answer.
This (along with finding the MEX) can be done in \mathcal{O}(N+\max(A)) time using a frequency table.
Since A_i \le 100 this is easily fast enough.

TIME COMPLEXITY:

\mathcal{O}(N + \max(A)) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    f = [0]*105
    for x in a: f[x] += 1
    
    m = 0
    while f[m] > 0: m += 1
    
    ct = 0
    for x in range(105):
        if x < m: ct += x*(f[x]-1)
        if x > m: ct += (x-m-1)*f[x]
    print('Alice' if ct%2 == 1 else 'Bob')