arya5691's blog

By arya5691, 12 years ago, In English

Hi,

I am unable to understand the solution for the following problem : http://codeforces.net/problemset/problem/255/E

I understand that we have to calculate the Sprague Grundy values for all numbers uptil root( 777777777777 ) = 881917. Then these values need to be used to calculate the function values for the number of coins in each of the piles, and these need to be XORed. If this final value is zero, then Rublo wins; else Furlo wins. I hope that my understanding is correct.

If yes, then how do I go about calculating the Sprague Grundy values ? I know that I need to find the minimum excludant of the function value for all the possible y values that can be reached from the current x, but I am not sure how I should do this efficiently.

The editorial says : "Grundy function is very small, you can start on the partial sums for each type of function that would quickly tell what function is in the interval, and which are not present. Knowing the answer is not difficult to find small response for all piles."

I am afraid I am unable to understand this. Could someone please elaborate ?

Thank you :)

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