Блог пользователя alphadr

Help to understand a Nim problem (game theory)
Автор alphadr, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes, Spraug-someone's theorem.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    → Ответить