Everything Nim
Contest: Codeforces Round 941 (Div. 1)
Difficulty rating: 1400
Tags: games, greedy, math, sortings

Alice and Bob are playing a game on $$$n$$$ piles of stones. On each player's turn, they select a positive integer $$$k$$$ that is at most the size of the smallest nonempty pile and remove $$$k$$$ stones from each nonempty pile at once. The first player who is unable to make a move (because all piles are empty) loses.

Given that Alice goes first, who will win the game if both players play optimally?

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of piles in the game.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the initial number of stones in the $$$i$$$-th pile.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, print a single line with the name of the winner, assuming both players play optimally. If Alice wins, print "Alice", otherwise print "Bob" (without quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Alice can win by choosing $$$k=3$$$ on her first turn, which will empty all of the piles at once.

In the second test case, Alice must choose $$$k=1$$$ on her first turn since there is a pile of size $$$1$$$, so Bob can win on the next turn by choosing $$$k=6$$$.

Example input:
7
5
3 3 3 3 3
2
1 7
7
1 3 9 7 4 2 100
3
1 2 3
6
2 1 3 4 2 4
8
5 7 2 9 6 3 3 2
1
1000000000

Example output:
Alice
Bob
Alice
Alice
Bob
Alice
Alice

Editorial:
If the smallest pile is of size $$$1$$$, then Alice must choose $$$k=1$$$ in her first move. Therefore, we can imagine subtracting $$$1$$$ from all piles, and determining who wins given that Bob goes first. We can repeat this process, switching the first player back and forth, until there is no longer a pile of size $$$1$$$. At this point, we are in one of two states:
1. If there are no piles remaining, the first player loses, because they cannot make any moves
2. Otherwise, the smallest pile is of size $$$x \ge 2$$$. We can show that the first player will always win. To do this, consider what happens if the first player chooses $$$k=x$$$:  If this would create a losing state for the next player, then the first player can choose $$$k=x$$$ and win.  Otherwise, the state reached by choosing $$$k=x$$$ is a winning state for the next player to move. So the first player can choose $$$k=x-1$$$, forcing the second player to choose $$$k=1$$$. The first player will now be in the winning state and can proceed to win the game.
3. If this would create a losing state for the next player, then the first player can choose $$$k=x$$$ and win.
4. Otherwise, the state reached by choosing $$$k=x$$$ is a winning state for the next player to move. So the first player can choose $$$k=x-1$$$, forcing the second player to choose $$$k=1$$$. The first player will now be in the winning state and can proceed to win the game.
To implement this solution, we only need to keep track of the largest pile size $$$a$$$, and the smallest positive integer $$$b$$$ that is not a pile size (essentially the MEX of the pile sizes, excluding $$$0$$$).
If $$$b > a$$$, then Alice and Bob will be forced to choose $$$k=1$$$ until the end of the game, so the parity of $$$a$$$ determines the winner. Otherwise, they will eventually reach a state with minimum pile size at least $$$2$$$, so the parity of $$$b$$$ determines the winner.
Complexity: $$$O(n)$$$ or $$$O(n\log n)$$$ depending on implementation