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.
- Maintain cnt[] where cnt[i]=no of times i occurs.
- odd=0;
- for i=1 to 500:
if cnt[i] is odd:
odd++; - if odd%2==1 print First
else print Second
I think this should work but I cant find a test case where this fails.
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!
Pretty interesting editorial! 
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
xor is 0 when we have two same values,so why is it that the above questions centers around even and odd rather missing the possibility of having all same no. of stones in piles or having odd/even no. of piles?
A really good problem, was XORing all the elements but overthinking of the corner cases didn’t allow me to submit even a single solution.