SRM 183, D2, 350-Pointer (CountGame)

James S. Plank

Wed Mar 1 20:20:59 EST 2017

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: 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;
}