Nim Game
Hard · rating 1750 · Game Theory, Bitmask
Two perfect players take turns; on a turn a player removes any positive number of stones from a single pile. Taking the last stone wins. The first line has k (the number of piles). The second line has the k pile sizes. Print FIRST if the first player wins with optimal play, else SECOND.
Constraints: 1 ≤ k ≤ 105
Editorial
Approach
This is classic Nim. The Sprague–Grundy theory says the position is losing for the player to move exactly when the XOR of all pile sizes is zero. So XOR the piles: non-zero means the first player can force a win, zero means the second player wins.
Why XOR
From any non-zero XOR you can always move to a zero-XOR position (handing your opponent a loss); from a zero-XOR position every move breaks it to non-zero.
x = 0
for pile in piles: x ^= pile
return 'FIRST' if x else 'SECOND'Complexity
Time: O(k). Space: O(1).
Related problems
- Shortest Delivery Tour — Hard