CODEWITHSUNDEEP
algorithm
Dreadly
Dreadly

Reputation: 45

Topcoder SRM 624 DIV II Level 3

Could anyone please explain the solution of this problem, you can check the problem here: http://community.topcoder.com/stat?c=problem_statement&pm=13204 and the solution here: http://apps.topcoder.com/wiki/display/tc/SRM+624

I actually don't understand how the calculation of nimbers and the choice of the minimum excluded ordinal has led to the solution.

Upvotes: 1

Views: 595

Answers (1)

Monica Muranyi
Monica Muranyi

Reputation: 131

I struggled a lot with this problem, I tried to solve it on my own after the SRM ended but couldn't find a solution so I decided to read the editorial.

The game presented in the problem is an impartial game using the normal play convention so based on the Sprague-Grundy theorem, it is equivalent to the game Nim, in which each state can be represented by a nimber.

The Nim game has been solved, even the combined Nim game consisting of multiple separate Nim heaps has been solved so there is a way of finding out which of the players has the winning strategy in this type of games. This is determined using nimbers which represent game states. If no move is possible from the current position, then the position gets nimber 0. Otherwise, according to the Sprague-Grundy theorem, the nimber of the position is the minimum non-negative integer that doesn't appear in the set of nimbers that can be reached in one move from the current position.

This paper helped me a lot in understanding nimber theory: http://web.mit.edu/sp.268/www/nim.pdf. As for the proof of the Sprague-Grundy theorem, I found the one from Wikipedia more easy to understand.

Upvotes: 4

Related Questions