Thanos Nim
Contest: Forethought Future Cup - Final Round (Onsite Finalists Only)
Difficulty rating: 2000
Tags: games

Alice and Bob are playing a game with $$$n$$$ piles of stones. It is guaranteed that $$$n$$$ is an even number. The $$$i$$$-th pile has $$$a_i$$$ stones.

Alice and Bob will play a game alternating turns with Alice going first.

On a player's turn, they must choose exactly $$$\frac{n}{2}$$$ nonempty piles and independently remove a positive number of stones from each of the chosen piles. They can remove a different number of stones from the piles in a single turn. The first player unable to make a move loses (when there are less than $$$\frac{n}{2}$$$ nonempty piles).

Given the starting configuration, determine who will win the game.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 50$$$) — the number of piles. It is guaranteed that $$$n$$$ is an even number.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — the number of stones in the piles.

Output format:
Print a single string "Alice" if Alice wins; otherwise, print "Bob" (without double quotes).

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

Note:
In the first example, each player can only remove stones from one pile ($$$\frac{2}{2}=1$$$). Alice loses, since Bob can copy whatever Alice does on the other pile, so Alice will run out of moves first.

In the second example, Alice can remove $$$2$$$ stones from the first pile and $$$3$$$ stones from the third pile on her first move to guarantee a win.

Example input:
2
8 8

Example output:
Bob

Example input:
4
3 1 4 1

Example output:
Alice

Editorial:
The main claim is that if a player is forced to reduce the minimum number of stones over all piles, then they lose. Intuitively, every time a player reduces the minimum, the other player has a move that doesn't reduce the minimum, and if a player isn't forced to reduce the minimum, they have a move that will force the other player to reduce the minimum.
More formally, let $$$m$$$ be the minimum number of stones in a pile, and let $$$x$$$ be the number of piles with $$$m$$$ stones. Alice can win if and only if $$$x \leq n/2$$$. Let's call the positions where Alice can win "winning positions", and all other positions "losing positions"
To see why this works, we need to show from a winning position, we can reach some losing position, and if we are at a losing position, we can only reach winning positions.
If we are at a winning position, there are at least $$$n/2$$$ piles that have strictly more than $$$m$$$ stones, so we can choose any arbitrary subset of them and reduce them to $$$m$$$ stones. This is now a losing position.
If we are at a losing position, no matter what we do, we must include a pile of size $$$m$$$ in our chosen subset. If $$$m$$$ is zero, this means we have no available moves. Otherwise, the minimum will strictly decrease, but only at most $$$n/2$$$ piles (from the piles that we chose) can reach that new minimum. Thus, losing positions can only reach winning positions.
The solution is then as follows. Find the min of the array and find the frequency of the min. Print "Alice" if the frequency is less than or equal to $$$n/2$$$, otherwise, print "Bob". The time complexity is $$$O(n)$$$. Alternatively, you can sort and check the index $$$0$$$ and index $$$n/2$$$ are the same for a short three line solution.