mohamedeltair's blog

By mohamedeltair, history, 7 years ago, In English

When the subgames are independent, dealing with them is easy, you try to calculate grundy for each sub game, either you derive a dynamic programming solution or see if the grundies follow specific pattern then just code the pattern directly (this is useful if the limits are very high), finally you xor the grundies.

But suppose a game like this: you have n piles and each pile has number of stones greater than 0, in a move you pick a number of stones to remove, this number will be subtracted from any pile which has a number of stones greater than or equal the number you have picked, as you see here one move affects more than one existing pile, how to think in these situations ?

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess this type of games will follow a pattern, that you need to discover.

check this problem here you can also read more about the situation when n=2 in here.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that the game you are describing is part of the solution to 850C - Арпа и игра с Можтабой. It can be solved using simple DP, as you can see in the editorial.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks all for your responses