Need an explanation of Grundy numbers from Competitive Programming Handbook

user_1143162 0
Viewed 36

I am trying to understand the example from the book https://cses.fi/book/book.pdf at page 239 . The example is described as follows: enter image description here

What I don't get is just what exactly, say, number 3 next to lower right corner means, we can move 4 steps up and 3 steps left from it, how is it 3? Same for 4 just above it, it doesn't correspond to any set of moves I can think of. The book in general makes a lot of leaps of logic they think are obvious but usually I can infer what they mean after some time, here I am just lost.

algorithm
1 Answers

The rule for computing these numbers is recursive.

You consider all the values you can reach, and then pick the smallest (non-negative) integer that is not reachable.

For example, the value in the top-left corner is 0 because no moves are possible.

For example, the value next to lower right is 3 because the reachable values are 0,4,1,0,2,1,4 so 3 is the smallest integer not in this list.

This explains how to compute the numbers, but to understand them it is probably better to start with understanding the game of Nim. In the game of Nim, the Sprague Grundy number for a pile is simply equal to the size of a pile.

user_11393930
Related