TC TCO08 Round 2 D1 500 (CreaturesTraining)

Category: Dynamic Programming
URL: http://www.topcoder.com/stat?c=problem_statement&pm=8570

This problem asks us to upgrade a set of creatures to maximise the final score after D days. The score is defined as the sum of the power level of the creatures. This is a tricky problem to solve efficiently. The key observation to make is that you never downgrade creatures and you can also skip creatures. Therefore this suggests that we can go from the leftside to rightside in a linear fashion. We can do a rough sketch of the recursive state as:

D(idx, x) = the maximum number of points we can get when we are processing level idx of the creatures and we have x days left in credit to upgrade our creatures.

When we try to formulate our recurrence relation we run into a problem, the state does not fully describe the problem state as it does not keep track of which creatures we have upgraded so far. So we begin to re-formulate our DP state by incorporating the set of monsters we have upgraded so far, i.e. the modifications we have made to the count array. One obvious yet inefficient way is to keep track of the count array as part of the DP state. However, this is too large of a memory footprint and as a result causes our solution to become inefficient. However, it is a good starting point as we can re-use our observation before that we never look back at a previous level. With this in mind, we can simply just keep track of the current extra creatures we have upgraded so far and optimally decide how many of these to keep in each level. Therefore, our DP state becomes:

D(idx, x, carry) = the maximum number of points we can get when we are processing level idx of the creatures and we have x days left in credit to upgrade our creatures. Given that we are also carrying forth carry number of monsters from the previous level.

In each state we can choose between 0 to count[idx] + carry monsters to upgrade. Each of these are valid transitions/upgrades provided we have enough day credit to upgrade them. We need to check whether or not this state space fits within the memory constraints, as there are a maximum of 50 monster levels and 100 days and carries (as we cannot carry more than 100 as this will exceed the upper limit of day credits). So we are faced with a memory footprint of 50 * 100 * 100 = 500,000 64-bit integers which easily fits within the limit.

Lastly, we consider the base/terminating case, this is when we reach the last level of the creatures. We implicitly prune any transitions where we exceed the amount of remaining day credit, so we do not need to consider this in our terminating case.

Implementing the ideas above is rather simple and short:

class CreatureTraining {
public:
   long long maximumPower(vector <int>, vector <int>, int);
};

long long dp[51][111][111];
vector<int> _count;
vector<int> _power;

long long func(int idx, int day, int carry) {
   if (idx >= _count.size()) return dp[idx][day][carry] = 0;
   if (dp[idx][day][carry] != -1) return dp[idx][day][carry];
   long long res = 0;
   int mx = carry + _count[idx];
   for (int i = 0; i <= mx; i++) {
      // move a set of 0 -> mx monsters up to the next level
      // leave mx - i behind
      if (day - i >= 0) {
         res >?= func(idx+1, day - i, i) + (mx-i) * (long long)_power[idx];
      } else {
         break;
      }
   }
   return dp[idx][day][carry] = res;
}

long long CreatureTraining::maximumPower(vector <int> count, vector <int> power, 
      int D) {
   long long res = 0;
   memset(dp,-1,sizeof(dp));
   limitD = D; _count = count; _power = power;
   return res = func(0, D, 0);
}