wineColoredDays's blog

GRID GAME and xor trick
By wineColoredDays, history, 9 years ago, In English

I was unable to solve the problem GRID GAME ( GRID GAME ) during the recently conducted ICPC Preparatory Series by team Enigma . The reason being i couldn't write the correct code to check whether the xor of the series x, x+2, x+4, ..., x+2*m-2 is 0 or not . But, after the contest i saw several different approaches to the problem . Some of them involved just 5-10 lines of code whereas some involved 20-30 lines of code . I'm very interested in knowing your approach . Thanks in advance for sharing :)

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I tried a lot on this problem but alas couldn't get AC :\ Here is what i observed. If (x % 4 == 2 | x % 4 == 3) and x != 2 then no matter what the value of m is first player wil always win since xor of the series would never be zero. So x can be like: 3,6,7,10,11,14,15...

The second thing was all numbers that don't belong to the above series if xored 4/8/12/multiple of 4 times then the result will be zero. Eg: 5^7^9^11 = 0 and 5^7^9^11^13^15^17^19 = 0 Last thing if x == 2 then it works with multiple of 3/7/11/15.. times Eg: 2^4^6 = 0 and 2^4^6^8^10^12^14 = 0

Still got WA after implementing above logic, but i am unable to find out where i am going wrong

Edit: I got it i was missing on the base case when m == 0 so no move can be made and BOB will win. AC submission on the above logic: https://www.codechef.com/viewsolution/8857389

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your first assumption is completely wrong . Consider this case x = 6 and m = 1 . In this case , we have just one element i.e 6, and ALICE (player1) can take all of them , leaving BOB unable to make a move and will win thus .

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah i mistyped here. Fixed it now. It should be since xor would never be zero it will always the first player who will win. Also i got the mistake after checking others code and can't believe it its the stupid base case when m == 0 :| Here is link to submission: https://www.codechef.com/viewsolution/8857389

      → Reply