SRM 619, D1, 250-Pointer (SplitStoneGame)

James S. Plank

Writeup: Sat Nov 19 11:37:24 EST 2016
Latest revision: Fri Nov 13 10:07:32 EST 2020

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5: 472e56226ea49a5e3242ae0558aa1080
answers.txt. MD5: 385a642cf19ab793ed9313406e3f7050
Problem Given in Topcoder: May, 2014
Competitors who opened the problem: 679
Competitors who submitted a solution: 667
Number of correct solutions: 504
Accuracy (percentage correct vs those who opened): 74.21%
Average Correct Time: 14 minutes, 53 seconds.

In case Topcoder's servers are down, here is a summary of the problem:

You are playing a game composed of piles of stones.
The number of stones in each pile is given to you as input to your program.
The game is a two person game, and proceeds in turns.
When it is your turn, you must pick a pile of stones which has more than one stone. You then pick two other piles which have at least one stone each. You split the stones from your pile into two groups, and you add one group to one of the piles that you picked, and the other group to the other.
The two groups cannot be empty.
You'll note that at each turn, the number of piles shrinks by one.
The game ends when you cannot make a move.
The number of piles will be ≤ 50 initially. (That's topcoder's constraing. Mine is 1000).
The number of stones per pile will be ≤ 50 initially.
Return "LOSE" or "WIN", depending on whether the initial piles are a losing or winning position.

Examples (these are compiled into the main.cpp program):

Example	Input	Output	Comments
0	{ 1, 1, 1 }	"LOSE"	There is no pile with more than one stone, so you can't make a move.
1	{ 2, 2 }	"LOSE"	You can pick up a pile, but there is only one pile left.
2	{ 1, 1, 2 }	"WIN"	If you split the last pile into the other two, you have the previous game.
3	{1, 2, 3, 4, 3, 2, 2, 4, 3, 1, 4, 4, 1, 2, 4, 4, 1, 4, 3, 1, 4, 2, 1}	"WIN"
4	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 9, 1, 3, 1, 1, 1, 1, 1}	"LOSE"
5	{ 1, 2, 50}	"WIN"

Testing yourself

Besides the initial six examples, you can generate random input by giving higher values as the command line argument. It will take the argument mod 1000 and add one, and then generate random input. The shell script tests.sh should produce answers.txt.

Hints

There's a temptation on problems like this to figure out the answer using your brain. That may well be possible, but I prefer to see if dynamic programming works, because then I don't have to think as hard. Remember the Towers of Hanoi: when you solve it with recursion, you don't have to think about which disk to move first -- the recursion does it for you.

So with the problem, take a standard dynamic programming approach: Figure out how to solve it recursively, then make it faster through memoization, removing recursion, etc.

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 the state of the 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, 50 }. 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:

string WL(int O, int M);

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!