SRM 701, D1, 250-Pointer (PartisanGame)

James S. Plank

Tue Nov 8 18:27:56 EST 2016
I want you to solve this incrementally, and I have written up the steps that you should take. You can double-check correctness with the outputs that are here in this writeup. When the outputs are large, I have links to files.

Step 1: This is Dynamic Programming -- Spot the Recursion

I'll be honest with you -- I hate solving these "game" problems. I don't reason very well about them, so if you see the answer on your own, and you can hack it up quickly, then good for you -- go get a good score on Topcoder!

I solved this one without bothering to reason about the game at all. Although the constraints are way too high for you to solve this with vanilla Dynamic Programming, let's start there, and we'll figure out the constraints later.

The recursion is pretty straightforward. Let A(n) be true or false, and let it represent whether Alice wins when it's her turn, and the number of stones is n. Similarly, let B(n) be true or false, and represent whether Bob wins when it's his turn, and the number of stones is n.

Start with the base cases: If n is less than all of the numbers in a, then A(n) is false. Similarly, if n is less than all of the numbers in b, then B(n) is false.

Now, consider A(n) otherwise. If there is a value of a[i] for which B(n-a[i]) is false, then Alice can win the game by choosing a[i] stones. Bob will be left with (n-a[i]) stones, and he will lose. Therefore A(n) is true. Otherwise A(n) is false. The recursion for B(n) is very similar.

Start with that program -- just the recursive one without any memoization. Here's how I laid it out -- I added methods A() and B() to the class, and I put the arrays a and b into the class definition as well. I renamed the parameters to getWinner() -- that allowed me to name those vectors a and b without any naming conflicts. 

class PartisanGame {
  public:
    string getWinner(int n, vector <int> array_a, vector <int> array_b);
    bool A(int n);
    bool B(int n);
    vector <int> a;
    vector <int> b;
};

I implemented getWinner() so that it created a and b from array_a and array_b, and so that it called A(n). I implemented A() and B() using recursion -- I had them print out when they begin, when they end, and when they make recursive calls. Here's the output on the first topcoder examples. You should go ahead and write this up, and make sure your output matches mine on these first two examples: 

UNIX> a.out 0
A(7) - Called.
A(7) calling B(4).
B(4) - Called.
B(4) calling A(0).
A(0) - Called.
A(0) - Returning false.
A(0) returned false, so B(4) returns true.
B(4) returned true, so A(7) is continuing.
A(7) calling B(3).
B(3) - Called.
B(3) - Returning false.
B(3) returned false, so A(7) returns true.
Alice
UNIX> a.out 1
A(10) - Called.
A(10) calling B(9).
B(9) - Called.
B(9) calling A(5).
A(5) - Called.
A(5) calling B(4).
B(4) - Called.
B(4) calling A(0).
A(0) - Called.
A(0) - Returning false.
A(0) returned false, so B(4) returns true.
B(4) returned true, so A(5) is continuing.
A(5) - Returning false.
A(5) returned false, so B(9) returns true.
B(9) returned true, so A(10) is continuing.
A(10) - Returning false.
Bob
UNIX>
Examples 2, 3 and 4 are way too big to complete -- the recursion will blow up. However, you can check the first 20 lines or so: 
UNIX> a.out 2 | head -n 20
A(104982) - Called.
A(104982) calling B(104980).
B(104980) - Called.
B(104980) calling A(104978).
A(104978) - Called.
A(104978) calling B(104976).
B(104976) - Called.
B(104976) calling A(104974).
A(104974) - Called.
A(104974) calling B(104972).
B(104972) - Called.
B(104972) calling A(104970).
A(104970) - Called.
A(104970) calling B(104968).
B(104968) - Called.
B(104968) calling A(104966).
A(104966) - Called.
A(104966) calling B(104964).
B(104964) - Called.
B(104964) calling A(104962).
UNIX>
I've also added an example 5, where a = b = {1,2} and n=10. You get exponential blow-up with this example, but it only prints out 279 lines, so you can try it. I'm showing the first and last ten lines below. You can see all 279 lines in Step-1-Ex5.txt. Go ahead and double-check your program against examples 0, 1 and 5. 
UNIX> a.out 5 | head
A(10) - Called.
A(10) calling B(9).
B(9) - Called.
B(9) calling A(8).
A(8) - Called.
A(8) calling B(7).
B(7) - Called.
B(7) calling A(6).
A(6) - Called.
A(6) calling B(5).
UNIX> a.out 5 | tail
A(1) returned true, so B(3) is continuing.
B(3) - Returning false.
B(3) returned false, so A(4) returns true.
A(4) returned true, so B(6) is continuing.
B(6) - Returning false.
B(6) returned false, so A(7) returns true.
A(7) returned true, so B(9) is continuing.
B(9) - Returning false.
B(9) returned false, so A(10) returns true.
Alice
UNIX> a.out 5 | wc
     279    1191    7067
UNIX> a.out 5 > Step-1-Ex5.txt
UNIX>

Step 2: Add the memoization cache

Now do step two of dynamic programming -- add the memoization cache. In this case, you'll need two caches -- one for A() and one for B(). In my code, I named the caches ACache and BCache, and both caches stored integers: 0 for false, 1 for true, and -1 for uninitialized.

In my code, I printed a line when I got answers from the cache. You can now see that the solution for example 5 is much shorter -- 90 lines instead of 279. That output is in Step-2-Ex5.txt. Examples 0 and 1 are unchanged, because they never use the cache. 

UNIX> a.out 5 | head
A(10) - Called.
A(10) calling B(9).
B(9) - Called.
B(9) calling A(8).
A(8) - Called.
A(8) calling B(7).
B(7) - Called.
B(7) calling A(6).
A(6) - Called.
A(6) calling B(5).
UNIX> a.out 5 | tail
A(8) returned true, so B(9) is continuing.
B(9) calling A(7).
A(7) - Called.
A(7) calling B(6).
B(6) comes from the cache -- false.
B(6) returned false, so A(7) returns true.
A(7) returned true, so B(9) is continuing.
B(9) - Returning false.
B(9) returned false, so A(10) returns true.
Alice
UNIX> a.out 5 > Step-2-Ex5.txt
UNIX> wc Step-2-Ex5.txt
      90     419    2460 Step-2-Ex5.txt
UNIX>
Unfortunately, while example 2 should be doable, it's not, because there are too many levels of recursion. On my computer, it seg faults while calling B(35192). 
UNIX> a.out 2

.....

B(35196) - Called.
B(35196) calling A(35194).
A(35194) - Called.
A(35194) calling B(35192).
Segmentation fault
UNIX>

Step 3: Remove the recursion

Your next step is to remove the recursion. Because all of the recursive calls are to smaller numbers, you can build both caches from small numbers to big numbers. In other words, start with ACache[0] and BCache[0], then ACache[1] and BCache[1], then ACache[2] and BCache[2], and so on. Here are the outputs of examples 0, 1 and 5. I have the output for example 2 in Step-3-Ex2.txt. 
UNIX> a.out 0
ACache[0] = 0
BCache[0] = 0
ACache[1] = 0
BCache[1] = 0
ACache[2] = 0
BCache[2] = 0
ACache[3] = 1
BCache[3] = 0
ACache[4] = 1
BCache[4] = 1
ACache[5] = 1
BCache[5] = 1
ACache[6] = 1
BCache[6] = 1
ACache[7] = 1
BCache[7] = 0
Alice
UNIX> a.out 1
ACache[0] = 0
BCache[0] = 0
ACache[1] = 1
BCache[1] = 0
ACache[2] = 1
BCache[2] = 1
ACache[3] = 0
BCache[3] = 1
ACache[4] = 0
BCache[4] = 1
ACache[5] = 0
BCache[5] = 1
ACache[6] = 0
BCache[6] = 1
ACache[7] = 0
BCache[7] = 1
ACache[8] = 0
BCache[8] = 1
ACache[9] = 0
BCache[9] = 1
ACache[10] = 0
BCache[10] = 1
Bob
UNIX> a.out 5 
ACache[0] = 0
BCache[0] = 0
ACache[1] = 1
BCache[1] = 1
ACache[2] = 1
BCache[2] = 1
ACache[3] = 0
BCache[3] = 0
ACache[4] = 1
BCache[4] = 1
ACache[5] = 1
BCache[5] = 1
ACache[6] = 0
BCache[6] = 0
ACache[7] = 1
BCache[7] = 1
ACache[8] = 1
BCache[8] = 1
ACache[9] = 0
BCache[9] = 0
ACache[10] = 1
BCache[10] = 1
Alice
UNIX> a.out 2 > Step-3-Ex2.txt
UNIX> tail -n 1 Step-3-Ex2.txt
Alice
UNIX>
Go ahead and implement this, and double-check it with the output above. You'll find that this was a lot easier to program than the solutions with recursion.

Step 4: There has to be a pattern, doesn't there?

The constraints on n are too big for this approach to work. You don't get 1,000,000,000 operations in Topcoder. However, there has to be a pattern, don't you think? Especially with the elements of a and b limited to being in the set {1,2,3,4,5}.

Here's what I did. I figured that after a certain point, ACache[] repeats its answers on a cycle. I don't know what that cycle is, but I bet it's smaller than, say, 5!, which is 120. So, if n is too big (say, greater than 1000), then what I did was create ACache[] to have 1001 elements. I then tried all possible cycle sizes from 1 to 120, and tested to see whether ACache[] answers followed that cycle size. If so, I used the cycle size and ACache to determine my answer. My hunch was that there would never be a case that didn't have a cycle size less than 121, and I was right. So much for math and reasoning!

Let me try to motivate the solution a little. Take a look at the first 30 values of ACache in Examples 2, 3 and 4: 

UNIX> a.out 2 | grep AC | head -n 30
ACache[0] = 0
ACache[1] = 0
ACache[2] = 1
ACache[3] = 1
ACache[4] = 1
ACache[5] = 1
ACache[6] = 1
ACache[7] = 1
ACache[8] = 1
ACache[9] = 1
ACache[10] = 1
ACache[11] = 1
ACache[12] = 1
ACache[13] = 1
ACache[14] = 1
ACache[15] = 1
ACache[16] = 1
ACache[17] = 1
ACache[18] = 1
ACache[19] = 1
ACache[20] = 1
ACache[21] = 1
ACache[22] = 1
ACache[23] = 1
ACache[24] = 1
ACache[25] = 1
ACache[26] = 1
ACache[27] = 1
ACache[28] = 1
ACache[29] = 1
UNIX> 

UNIX> a.out 3 | grep AC | head -n 30
ACache[0] = 0
ACache[1] = 0
ACache[2] = 0
ACache[3] = 0
ACache[4] = 1
ACache[5] = 1
ACache[6] = 1
ACache[7] = 1
ACache[8] = 1
ACache[9] = 0
ACache[10] = 0
ACache[11] = 0
ACache[12] = 0
ACache[13] = 1
ACache[14] = 1
ACache[15] = 1
ACache[16] = 1
ACache[17] = 1
ACache[18] = 0
ACache[19] = 0
ACache[20] = 0
ACache[21] = 0
ACache[22] = 1
ACache[23] = 1
ACache[24] = 1
ACache[25] = 1
ACache[26] = 1
ACache[27] = 0
ACache[28] = 0
ACache[29] = 0
UNIX> 

UNIX> a.out 4 | grep AC | head -n 30
ACache[0] = 0
ACache[1] = 1
ACache[2] = 1
ACache[3] = 1
ACache[4] = 1
ACache[5] = 1
ACache[6] = 0
ACache[7] = 1
ACache[8] = 1
ACache[9] = 1
ACache[10] = 1
ACache[11] = 1
ACache[12] = 0
ACache[13] = 1
ACache[14] = 1
ACache[15] = 1
ACache[16] = 1
ACache[17] = 1
ACache[18] = 0
ACache[19] = 1
ACache[20] = 1
ACache[21] = 1
ACache[22] = 1
ACache[23] = 1
ACache[24] = 0
ACache[25] = 1
ACache[26] = 1
ACache[27] = 1
ACache[28] = 1
ACache[29] = 1
UNIX>

You can see that in example 2, the cycle size is one. In example 3, the cycle size is nine, and in example 4, the cycle size is six. That means, for example, that in example 3, ACache repeats itself every nine entries, and in example 4, it repeats itself every six entries.

Example 2 is a little problematic, because ACache clearly repeats itself every entry, but starting with entry 2, not entry 0.

So, if we want to discover the cycle size, we're going to have to start with some entry greater than zero. What I did was the following. I wrote a procedure called is_cycle(c). What this did was start at the smallest index greater than or equal to 200 that is a multiple of c. Call that value s. For every value of i from s to 1000, I then checked to make sure that ACache[i] is equal to ACache[i-c]. If that's true, then is_cycle(c) is true. Otherwise, is_cycle(c) is false.

Once you find the value of c, you use it to calculate A(n), even if n is huge. What you do is calculate r = n%c, and then you return Acache[s+r].

Let's use example 3 as our guide. Here are the values of ACache[190] through ACache[219]: (I got these with: "a.out 3 | grep ACache | sed -n 191,220p"). 

ACache[190] = 0
ACache[191] = 0
ACache[192] = 0
ACache[193] = 1
ACache[194] = 1
ACache[195] = 1
ACache[196] = 1
ACache[197] = 1
ACache[198] = 0
ACache[199] = 0

ACache[200] = 0
ACache[201] = 0
ACache[202] = 1
ACache[203] = 1
ACache[204] = 1
ACache[205] = 1
ACache[206] = 1
ACache[207] = 0
ACache[208] = 0
ACache[209] = 0

ACache[210] = 0
ACache[211] = 1
ACache[212] = 1
ACache[213] = 1
ACache[214] = 1
ACache[215] = 1
ACache[216] = 0
ACache[217] = 0
ACache[218] = 0
ACache[219] = 0

Now, let's see what happens when we try to discover cycles of each size from 1 to 9: Once we discover that the cycle is of size 9, we can solve the problem for n = 999999999. We set r = n%9 = 0. We then return ACache[s+r] = ACache[207] = 0. The answer is "Bob".

Program this up -- this is your last revision. To help you double-check your code, I've instrumented my program to either print when the answer comes from the cache, or to print all of the is_cycle() calls, and then do the final arithmetic when is_cycle(c) is true: 

UNIX> a.out 0
The answer comes from the cache.  ACache[7] = 1.
Alice
UNIX> a.out 1
The answer comes from the cache.  ACache[10] = 0.
Bob
UNIX> a.out 2
is_cycle(1): s = 200.  True
r = n%c = (104982)%(1) = 0. ACache[200+0] = 1
Alice
UNIX> a.out 3
is_cycle(1): s = 200.  False because ACache[202] != ACache[201]
is_cycle(2): s = 200.  False because ACache[202] != ACache[200]
is_cycle(3): s = 201.  False because ACache[202] != ACache[199]
is_cycle(4): s = 200.  False because ACache[200] != ACache[196]
is_cycle(5): s = 200.  False because ACache[200] != ACache[195]
is_cycle(6): s = 204.  False because ACache[204] != ACache[198]
is_cycle(7): s = 203.  False because ACache[205] != ACache[198]
is_cycle(8): s = 200.  False because ACache[201] != ACache[193]
is_cycle(9): s = 207.  True
r = n%c = (999999999)%(9) = 0. ACache[207+0] = 0
Bob
UNIX> a.out 4
is_cycle(1): s = 200.  False because ACache[204] != ACache[203]
is_cycle(2): s = 200.  False because ACache[200] != ACache[198]
is_cycle(3): s = 201.  False because ACache[201] != ACache[198]
is_cycle(4): s = 200.  False because ACache[202] != ACache[198]
is_cycle(5): s = 200.  False because ACache[203] != ACache[198]
is_cycle(6): s = 204.  True
r = n%c = (1000000000)%(6) = 4. ACache[204+4] = 1
Alice
UNIX> a.out 5
The answer comes from the cache.  ACache[10] = 1.
Alice
UNIX>
Compile, submit!