alphadr's blog

Help to understand a Nim problem (game theory)
By alphadr, 11 years ago, In English

Problem: http://www.lightoj.com/volume_showproblem.php?problem=1393

The problem is categorized as Nim in LightOJ. I solved the remaining 4 problems in the same category with no major difficulties (here), however I am stuck on this one.

Could someone please hint to the solution ? Is it only "basic" Nim, or is there something else I need to learn ?

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, Spraug-someone's theorem.

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

    Thanks. I haven't yet reached Sprague-Grundy theorem, nice to know it wasn't a variant of normal nim.

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

      FYI, I havent read the problem u mentioned.

      And also, every impartial game gets down to nim : ) sorry to frustrate you : ]. But yes, most of algorithmic problems are hard enough to see correspondence between them and the game of nim. Here comes the theorem...

      Good luck.

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

About this problem — it’s a staircase nim on a grid, so we must xor value on the cell (x,y) with answer if (x + y) mod 2 != (r + c) mod 2. For explanation about staircase nim try to google.
P.S. — AC code is here

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

    Thank you so much. Didnt know about staircase nim before. I found explanations for staircase nim, but not ones for it on a grid.

    Cold you please give a bit more insight how we treat the grid in this case as a single staircase ?

    → Reply