TWONIM - Editorial

PROBLEM LINK:

Contest
Practice

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

6 Likes

Now, after trying on these examples, we can generalize the if n is odd, then first player will lose, otherwise he will win.
QUICK EXPLANATION:
If A1⊕A2⊕A3⋯⊕AN=0A1⊕A2⊕A3⋯⊕AN=0, then the first player wins.
Otherwise
If N is odd, then first player will win.
If N is even, then the second player will win.

So, much funny

2 Likes

Thought too much and executed very little on the simple lines,I was thinking about too many different testcases. :frowning: Was worrying about the counts of same number stone piles, when the trick was

  • XOR mattered only for the very first time at the start
  • after that all it mattered was odd or even

Nice problem !!

1 Like

Damn, I actually XORed each element with the full set’s XOR to see if it could be removed (i.e. it did not lead to a zero) and accordingly removed that element. It worked but this is neat.

1 Like

Can anyone give a test case where this algorithm fails.

  1. Maintain cnt[] where cnt[i]=no of times i occurs.
  2. odd=0;
  3. for i=1 to 500:
    if cnt[i] is odd:
    odd++;
  4. if odd%2==1 print First
    else print Second

I think this should work but I cant find a test case where this fails.

@prateekjjw001

Your algorithm fails for the following case:

1

1

1

1 Like

I simply simulated playing of whole game. A player will try to remove that pile after whose removal there is remaining piles with non zero XOR.Since constraints were very small so it got executed. Link

2 Likes

your logic fails in

1
6

3 3 3 3 3 2

your_o/p : First

Actual_o/p : Second

it will also depends on the maximum frequency of a input numbers

prateekjjw001

i have a case in which your logic fails

1

8

5 4 3 3 3 3 3 2

you can visit my solution for better understanding
https://www.codechef.com/viewsolution/9709264

Very nice problem!

@arunmittal53
how second wins in this test case
1
6
3 3 3 3 3 2
can u explain?

Pretty interesting editorial! :slight_smile:

Weak test cases.

https://www.codechef.com/viewsolution/9709264

The above solution prints “Second” for the following case:

1

4

3 3 3 2

The correct answer is “First”.

Someone please clear my doubt by giving a test case.I didn’t checked the first condition of xoring all elements and checking if its zero…directly checked if N is odd or even.Because I feel that there is no way of getting xor=0 if N is odd.Someone please prove me wrong!

What will the output when the input is :
1
4
2 2 1 3
In this case, the correct answer should be Second.
But above stated method gives First.

@ashubaplawat there are many ways for the first to win , one of them is : (1,1,2,2,3,4) -> (1,1,2,2,3)
-> (1,1,2,3) -> (1,1,3) -> (1,3) -> 1 -> 3

Awesome Editorial!

2 Likes

1 2 3 10 10 10 10

did the same thing, can anybody explain why our solution is wrong

I think the answer should be First only. Say first player removes pile with number 2 then i have 5 piles with same number so the second player will remove one of those piles leaving equal piles in even numbers so answer of XOR is zero hence first wins. Do comment if i am wrong