SRM 619, D1, 250-Pointer (SplitStoneGame)
James S. Plank
Sat Nov 19 11:37:24 EST 2016
There's one big observation to make, which makes this problem much simpler than
it appears. That is that if a pile has more than one stone, then it doesn't matter
how many stones it has. You can thus represent your piles with two values, "one" and
"more than one." To help you see this, consider the example from the problem writeup,
where the piles are { 1, 2, 25 }. Instead, you can represent them as:
{ one, more-than-one, more-than-one }.
Any move that Shiny makes will turn the piles into:
{ more-than-one, more-than-one }.
And that's a losing state for whoever is playing Shiny!
Now, after working through that example, you can observe that you don't need a
big array to hold the game state. You just need two numbers:
- O: The number of piles with exactly one stone.
- M: The number of piles with more than one stone.
The examples can be represented as follows:
- Example 0: O = 3 and M = 0.
- Example 1: O = 0 and M = 2.
- Example 2: O = 2 and M = 1.
- Example 3: O = 6 and M = 17.
- Example 4: O = 20 and M = 4.
So, write a method with the following prototype:
This returns whether one wins or loses when there are O piles with one stone,
and M piles with more than one stone. I will leave it to you to figure out the
base cases, and the recursion.
You can solve all of the examples without memoization, so that you can see the answers.
Examples 3 and 4 will be too slow, though, so you should then memoize. Then, you're done!