PROBLEM LINK:
Authors: Jaub Safin
Testers: Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Praveen Dhinwa
DIFFICULTY:
Easy
PREREQUISITES:
Game theory, parity observation
PROBLEM:
Two players play a game. Game consists of N piles each consisting of some stones, you are given the information about it in an array A, such that A_i denotes number of stones in i-th pile.
If before a turn of a player, bitwise XOR of all the numbers is zero, then that player wins.
In each turn, a player has to choose some pile and remove all of the stones from it. That pile will become empty and is removed from the game.
Note that if there is no pile left, we still define the xor of zero files as zero.
If both the players win optimally, find out who will win the game?
QUICK EXPLANATION:
-
If A_1 \mathbin{\oplus} A_2 \mathbin{\oplus} A_3 \dots \mathbin{\oplus} A_N = 0, then the first player wins.
-
Otherwise
- If N is even, then first player will win.
- If N is odd, then the second player will win.
You can get this observations by working on smaller examples of N = 1, 2, 3.
Hard part is to come up the observation, proving it would be quite simple.
EXPLANATION:
Simplest case
If the xor of all numbers before the game is zero, then obviously first player will win the game.
Try finding a pattern
Now, we will take the case when xor of all numbers A_1 \mathbin{\oplus} A_2 \mathbin{\oplus} A_3 \dots \mathbin{\oplus} A_N is non-zero.
Let us start with some simple cases and try to find some pattern.
n = 1
We have only one pile. A_1 \neq 0.
First player will remove the first pile. Now there is no pile in the game. According to definition in the problem, xor of zero piles is also considered zero. So, the second player wins the game.
Hence, we can say that n = 1 is losing for current player.
n = 2
We have two piles A_1, A_2, such that A_1 \mathbin{\oplus} A_2 \neq 0, i.e. A_1 \neq A_2.
First player can choose any of the piles A_1 and A_2 and remove it. The second player will be left with only one pile with non-zero stones in it.
Now, we have 1 pile with non-zero stones in it. This case is same as the previous one, in which the player whose turn it is will lose the game.
So, second player will lose the game.
So, we can say that n = 2 is a winning position for current player.
n = 3
Let us say the piles are A_1, A_2, A_3 such that A_1 \mathbin{\oplus} A_2 \mathbin{\oplus} A_3 \neq 0.
First player can remove any of A_1, A_2, A_3.
Now the first player has two options
- Remove a pile such that xor of remaining piles is zero.
In this case, first player will lose the game. - Remove a pile such that xor of remaining piles is non-zero.
In this case, the second player will be left with two piles such that their xor is non-zero. We have already noted that n = 2 with xor of all elements non-zero is a winning position for the current player (i.e. second player).
So, first player will again the lose the game.
In summary, n = 3 is a losing position for first player.
Now, after trying on these examples, we can generalize the if n is odd, then first player will lose, otherwise he will win.
Proof of the generalization by induction
Induction Hypothesis
If xor of all numbers is non-zero, then n = odd is a losing position and n = even is a winning position.
We can prove this by induction.
Base Case
We have already taken the base case n = 1.
Induction step
Now, assume that the hypothesis is true till n < N.
Case 1: N is even.
First player can remove any of the piles such that xor of remaining piles is non-zero. We can prove that first player can always find such a pile.
Proof by contradiction
Let X = A_1 \mathbin{\oplus} A_2 \mathbin{\oplus} A_3 \dots \mathbin{\oplus} A_N.
We have X \neq 0.
Assume the contrary, i.e. whatever pile we remove, the xor of the remaining piles is zero.
Xor of piles after removing pile A_i will be X \mathbin{\oplus} A_i.
So, we have X \mathbin{\oplus} A_i = 0 for all 1 \leq i \leq N.
Let us take the xor of all of the N equations.
We get X \mathbin{\oplus} X \dots (N \text{ times}) \quad \mathbin{\oplus} A_1 \mathbin{\oplus} A_2 \mathbin{\oplus} A_3 \dots \mathbin{\oplus} A_N = 0
As A_1 \mathbin{\oplus} A_2 \mathbin{\oplus} A_3 \dots \mathbin{\oplus} A_N = X
\implies X \mathbin{\oplus} X \dots ((N+1) \text{ times}) = 0
As N is even, i.e. N + 1 is odd. So we get X = 0.
But we started with saying that X \neq 0, but got X = 0 which is a contradiction.
Hence proved.
So, now we know that first player can find a pile in such a way that xor of remaining piles N - 1 is non-zero. As know that N - 1 is odd. By induction hypothesis, the position after the current move is a losing position, hence this position will be a winning position.
Case 2: N is odd.
First player can not remove a pile A_i such that xor of remaining number is zero, because then the second player will win.
Now, take the other case when the xor of remaining N - 1 number is non-zero. As we know that N - 1 is even and from the induction hypothesis, we can say that the position after the current move will be a winning position for second player. Hence, it is a losing position for first player.
Pseudo Code
int ans = 0;
for (int i = 1; i <= N; i++) {
ans ^= a[i];
}
boolean isWinningPosition = true;
if (ans != 0) {
if (n % 2 == 1) {
isWinningPosition = false;
}
}
puts(isWinningPosition ? "First" : "Second");
Time Complexity:
We just have to iterate over all the elements of the arary only once and compute xor of all elements. All of these operations can be done in \mathcal{O}(N) time.
Was worrying about the counts of same number stone piles, when the trick was