TWONIM - Editorial

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

Your code gives wrong answer for this test case.

1

3

1 2 3

Your answer - Second

Correct answer - First