Valley Of Death - help

This is question of the Alkhwarism 2013 contest which has ended

Question : Valley Of Death

I wasn’t able to come to a solution during the contest but still not able to understand the concept of grundy numbers used in it even after reading other people’s codes

Can someone please take a min and explain it

Thanks

if i look at that solution, the answer seems quite simple.

have a look at the solve() function :

  1. it computes the possibles values of the number of coins you can remove each turn (F in pb statement, in here)
  2. it simulates the game in a dynamic programming matrix the optimal way (two dimensions for two players)
  3. it stores already computed solutions in a cache map called M
  4. then for each pile, the solution is XORed with the previous computed one, to find the final answer

hope it helps !

1 Like

Can anyone pls explain this part?Thanks in advance :slight_smile:

  ctr++;
  	rep(j, ptr)
       if(in[j] > i)
           break;
       else
           v[dp2[i-in[j]]] = ctr;`