Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Foysal_Ahmmed's blog

By Foysal_Ahmmed, history, 2 years ago, In English,

I have just started to learn Sprague-Grundy Number. Now trying to solve lightoj 1296 — Again Stone Game this problem.

Alice and Bob are playing a stone game. Initially there are n piles of stones and each pile contains some stone range[1,10^9]. Alice start the game and they alternate moves. In each move, a player has to select any pile and should remove at least one and no more than half stones from that pile. Who will win the game.

I think it's not possible to solve by Dynamic Programming. Need to find out a pattern. I just calculate some values Sprague-Grundy Number and find a pattern for even number that each even number Sprague-Grundy Number is its own half. (I using term SGN as Sprague-Grundy Number). Like it – SGN(2) = 1, SGN(4) = 2, SGN(6) = 3, SGN(8) = 4.........

For some odd numbers it SGN(1)=0, SGN(3)=0, SGN(5)=1, SGN(7)=0,SGN(9)=2......... But I could not find out any pattern for odd numbers. I can not understand that my observations is right or wrong. Looking help for odd values pattern or a new hints to solve this problem.

Thanks in advance………………………….

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

SGN(N) = 0, If (N+1) Can Be represented as a power of 2 SGN(1) = SGN(3) = SGN(7) = SGN(15) = 0 and so on

Otherwise SGN(N) = x(This is Based on observation without any kind of proof)

as long as the number is not divisible by 2,keep dividing it by 2(integral division) then do an extra division by 2 after done

Again,I dont know how to prove this Would be glad if someone could provide a proof

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

    Oh that's great observation for odd numbers.Your process for odd numbers it work correctly it give the exact SGN value for each odd numbers .

    Thank you very much .