Prime Split Game
Contest: Pinely Round 4 (Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: bitmasks, dp, fft, games, math, number theory

Alice and Bob are playing a game with $$$n$$$ piles of stones, where the $$$i$$$-th pile has $$$a_i$$$ stones. Players take turns making moves, with Alice going first.

On each move, the player does the following three-step process:

1. Choose an integer $$$k$$$ ($$$1 \leq k \leq \frac n 2$$$). Note that the value of $$$k$$$ can be different for different moves.
2. Remove $$$k$$$ piles of stones.
3. Choose another $$$k$$$ piles of stones and split each pile into two piles. The number of stones in each new pile must be a prime number.

The player who is unable to make a move loses.

Determine who will win if both players play optimally.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the number of stones in the piles.

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, output "Alice" (without quotes) if Alice wins and "Bob" (without quotes) otherwise.

You can output each letter in any case (upper or lower). For example, the strings "alIcE", "Alice", and "alice" will all be considered identical.

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

Note:
In the first test case, there are $$$2$$$ piles of stones with $$$2$$$ and $$$1$$$ stones respectively. Since neither $$$1$$$ nor $$$2$$$ can be split into two prime numbers, Alice cannot make a move, so Bob wins.

In the second test case, there are $$$3$$$ piles of stones with $$$3$$$, $$$5$$$, and $$$7$$$ stones respectively. Alice can choose $$$k = 1$$$, remove the pile of $$$7$$$ stones, and then split the pile of $$$5$$$ stones into two piles of prime numbers of stones, $$$2$$$ and $$$3$$$. Then, the piles consist of $$$3$$$ piles of stones with $$$3$$$, $$$2$$$, and $$$3$$$ stones respectively, leaving Bob with no valid moves, so Alice wins.

In the third test case, there are $$$4$$$ piles of stones with $$$4$$$, $$$6$$$, $$$8$$$, and $$$10$$$ stones respectively. Alice can choose $$$k = 2$$$, removing two piles of $$$8$$$ and $$$10$$$ stones. She splits the pile of $$$4$$$ stones into two piles of prime numbers of stones, $$$2$$$ and $$$2$$$, and the pile of $$$6$$$ stones into two piles of $$$3$$$ and $$$3$$$ stones. Then, Bob has no valid moves, so Alice wins.

In the fourth test case, there are $$$5$$$ piles of stones, each containing $$$8$$$ stones. It can be shown that if both players play optimally, Bob will win.

Example input:
4
2
2 1
3
3 5 7
4
4 6 8 10
5
8 8 8 8 8

Example output:
Bob
Alice
Alice
Bob

Editorial:
Hint 1
Consider which pairs of numbers an odd number can be split into. What about an even number?
Hint 2
Consider a simplified version of the game with only two piles of stones, where the first pile contains $$$x$$$ stones, and the second pile contains one stone. Determine all winning positions for this game configuration.
Hint 3
For the simplified version of the game, given that we have calculated the odd x which are losing positions, we can quickly determine the winning positions for even x using Fast Fourier Transform or bitset operations.
Hint 4
We can determine the winner of most games by considering how many $$$a_i$$$ are in winning positions and whether $$$n$$$ is odd or even.
Hint 5
For games where we currently cannot determine the winner, we can use the number of $$$a_i$$$ that can be split into two winning positions to determine the final winner.
Solution
Let's analyze this problem from simple to complex scenarios.
First, let's consider how to split a single number $$$x$$$:
• For an odd number $$$x$$$, it can only be split into $$$x - 2$$$ and $$$2$$$. Proof: An odd number can only be split into an odd and an even number, and the only even prime is $$$2$$$.
• For an even number $$$x$$$, apart from $$$x = 4$$$ which can be split into $$$2$$$ and $$$2$$$, it can only be split into two odd numbers. Proof: An even number can only be split into odd and odd, or even and even. The only even prime is $$$2$$$, thus only $$$4$$$ can be split into even and even.
Next, let's consider a simplified version of the game with only two piles of stones, where the first pile contains $$$x$$$ stones, and the second pile contains one stone. If Alice wins in this setup, we call $$$x$$$ a winning position; otherwise, it is a losing position. We first determine whether an odd $$$x$$$ is a winning position, then determine whether an even $$$x$$$ is a winning position:
• For an odd $$$x$$$, we need to calculate how many times $$$2$$$ stones can be split from $$$x$$$ until $$$x - 2$$$ is not a prime. If the number of splits is odd, then it is a winning position; otherwise, it is a losing position.
• For an even $$$x$$$, if $$$x$$$ can be split into two losing positions, then $$$x$$$ is a winning position; otherwise, $$$x$$$ is a losing position. Apart from $$$x = 4$$$ (a winning position), other even numbers can only be split into two odd numbers. Optimization: Directly checking all ways to split each even number will time out. However, we can use the Fast Fourier Transform (FFT) or bitset operations, based on the losing positions of odd numbers, to determine the winning positions of even numbers. If you are not familiar with this optimization technique, it is recommended to first solve 2014 ICPC SWERC Problem C Golf Bot, the tutorial is here.
In summary, the characteristics of winning and losing positions are: losing positions either cannot be split, or they must split out at least one winning position. Winning positions can be split into two losing positions.
Let's return to the original game. If all $$$a_i$$$ are in losing positions, Bob will win. Proof: No matter how Alice moves, Bob can always turn all $$$a_i$$$ back to losing positions. Suppose Alice splits to produce $$$2 \cdot k$$$ new piles in one move, then at least $$$k$$$ of them will be in winning positions. Bob can split these $$$k$$$ piles into $$$2 \cdot k$$$ losing positions and remove the remaining $$$k$$$ new piles. As a result, all piles will be back in losing positions. This process will continue until no more losing positions can be split, which will lead to Bob's win.
Since we now have a general scenario where Bob wins, we can discuss all scenarios that can turn into this scenario with one move. In these scenarios, Alice will win:
• When $$$n$$$ is even and the number of winning positions $$$a_i$$$ ranges between $$$[1, n]$$$, Alice will win. Proof: Assuming the number of winning positions is $$$w$$$, Alice can choose $$$k = \lceil \frac{w}{2} \rceil$$$ to select $$$k$$$ winning positions and split them into $$$2 \cdot k$$$ losing positions. She then removes other winning positions and may remove one extra pile, to sum up $$$k$$$ piles. After the move, all piles will be turned into losing positions, ensuring Alice's win.
• When $$$n$$$ is odd and the number of winning positions $$$a_i$$$ ranges between $$$[1, n-1]$$$, Alice will win. Proof: Similar to the previous proof, Alice can turn all piles into losing positions in one move.
The only unresolved case is when $$$n$$$ is odd and the number of winning positions $$$a_i$$$ equals $$$n$$$. Alice cannot turn all positions into losing positions in one move because at most $$$2 \cdot k$$$ positions can be changed in a single move. Since $$$2 \cdot k < n$$$, it is impossible to change all $$$n$$$ positions. In this case, if someone splits a winning position into a losing position, the number of winning positions will drop to $$$[1, n-1]$$$, leading to failure. However, winning positions can sometimes be split into two winning positions. Therefore, we only need to consider this splitting case.
A number is called a good position if it can be split into two winning positions; otherwise, it is called a bad position. We find that odd numbers cannot be good positions because they can only be split into $$$x-2$$$ and $$$2$$$, and $$$2$$$ is not a winning position. Thus, only even numbers can be good positions if they can be split into two odd winning positions. Optimization: Directly checking ways to split each even number will time out. We can use FFT or bitset operations to identify good positions among even numbers.
Note that good positions can only be split into two bad positions because even numbers can only be split into odd numbers or $$$2$$$, both of which are considered bad positions. Thus, when $$$n$$$ is odd and all $$$a_i$$$ are in winning positions, we only need to determine the winner based on the number of good positions:
• If the number of good positions $$$a_i$$$ is $$$0$$$, Bob will win. Proof: Any move by Alice will produce losing positions, as analyzed earlier, leading to failure.
• If the number of good positions $$$a_i$$$ is between $$$[1, n-1]$$$, Alice will win. Proof: In one move, Alice can turn all numbers into bad positions using a method similar to when $$$n$$$ is odd and winning positions are between $$$[1, n-1]$$$.
• If the number of good positions $$$a_i$$$ is $$$n$$$, Bob will win. Proof: Any move by Alice will produce losing or bad positions, ultimately leading to the previous scenario and resulting in failure.