SRM 183, D2, 350-Pointer (CountGame)

James S. Plank

Wed Mar 1 20:20:59 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2009
Competitors who opened the problem: 233
Competitors who submitted a solution: 163
Number of correct solutions: 104
Accuracy (percentage correct vs those who opened): 44.64%
Average Correct Time: 22 minutes, 11 seconds.

I'm going to save you some time. (Maybe). Don't think about how to win the game. Instead, think about dynamic programming. You can solve this with recursion:

The base case is when you can win the game in one move. Return the answer.
Otherwise, for each value of i from 1 to maxAdd, call the method recursively on (next+i). If the answer is -1, then your opponent has lost, so i is your answer. If the answer is anything but -1, then you need to try another value of i.
If you can't find a value of i that lets you win the game, then you lose. Return -1.

Go ahead and solve it in this manner. I've added a 4th example to main.cpp that sets goal to 1000, next to one and maxAdd to 8. You'll see that your recursive solution takes too long now, so you need to memoize by adding a cache.

My Solution

My solution is in Solution.cpp:

/* Topcoder SRM 183, D2, 350-pointer.
   CountGame
   James S. Plank
   Wed Mar  1 20:35:06 EST 2017
 */

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

/* I've added a cache for dynamic programming to the class. */

class CountGame
{
    public:
        int howMany(int maxAdd, int goal, int next);
        vector <int> cache;
};

int CountGame::howMany(int maxAdd, int goal, int next)
{
    int i;

    /* The first time that this is called, I initialize the cache.
       My "empty" value is -2.  This is because -1 is a valid answer. */

    if (cache.size() == 0) cache.resize(goal+1, -2);

    /* Check the cache and return if I've already solved this value of next. */

    if (cache[next] != -2) return cache[next];

    /* Here's the base case of the recursion.
       If I can solve the problem in one move, then I return that move. */

    if (goal - next + 1 <= maxAdd) return goal-next+1;

    /* Now I go through and test every value of i from 1 to maxAdd.
       If my opponent loses after I add i to next, then I win! */

    for (i = 1; i <= maxAdd; i++) {
        if (howMany(maxAdd, goal, next+i) == -1) {
            cache[next] = i;
            return i;
        }
    }

    /* Otherwise, I lose.  :(  */

    cache[next] = -1;
    return -1;
}