Can anyone help me with this problem?

I have learnt sprague grundy numbers recently.

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | wxhtxdy | 3276 |

7 | LHiC | 3276 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 172 |

4 | Vovuh | 165 |

4 | PikMike | 165 |

4 | antontrygubO_o | 165 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

Can anyone help me with this problem?

I have learnt sprague grundy numbers recently.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 10:55:12 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

First, to use NIM game technique you need independent games. You can think of the game as moving coins from i to 2*i, 3*i or 5*i. And each coins is independent from the rest.

Now, you just need to find the grundy number associated with each coin. To do this you can build an graph. Where each position of the array is a node, and an edge represents to which positions you can move the coin. For example for a array of size 10:

In red is the grundy number. Basically if you can't go anywhere it is 0, otherwise is the smallest integer that you can't directly reach.

To solve the problem you can pre-calculate the grundy number for each position with the graph. Then do XOR for the grundy number of each coin.

"Then do XOR for the grundy number of each coin."

for each coin or position?

For each coin.

For example:

0 3 0 1 2 0 0 0 0 0

You have 3 coins in position 2, 1 coin in position 4 and 2 in position 5. So you should do:

`grundy(2) XOR grundy(2) XOR grundy(2) XOR grundy(4) XOR grundy (5) XOR grundy(5)`

Obs: Just remember that

`a XOR a = 0`

, so the above is equivalent to:`grundy(2) XOR grundy(5)`

Can you please explain why ? If we are doing this we can just store in the array 0 1 0 1 0 0 0 0 0 0 and then grundy(2) xor grundy(4)