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>
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>
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.
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 |
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!