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)

https://pastebin.com/xpAS7sXJ

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 .