TC SRM424 D1 600 (StrengthOrIntellect)

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

This problem asks us to determine the maximum number of missions we can complete given two character attributes: strength and intellect. We meet the pre-requirements to complete a mission if either one of the strength or intellect attributes are at least as high/equal to the mission's strength and intellect requirements respectively.

A greedy approach does not work here. You can informally argue by noting that when we are given two choices to increase strength or intellect, there is no clear decision on which option to choose. The local optimality does not hold for the global optimality, as if we choose one or the other we might miss out on earning a lot of points which will allow us to complete more missions. Another greedy heuristic might be to try both maximising strength and maximising intellect and choose the maximum number of missions from the two possible options. This also does not work because the optimal solution might not be on a extreme point of strength or intellect. Since the decisions we make need to be flexible enough to change between increasing strength and/or then increasing intellect or vice-versa, it's rather clear that no amount of heuristics will pass all the (corner) test cases.

The next obvious approach to consider is brute force. We can keep track of which missions we have accomplished and how much strength and intellect we have achieved so far, then for all possible mission transitions recurse along the mission and adjust the strength and intellect. In effect, this almost works if we memoise the solution. The problem is keeping track of the missions we have completed - the naive approach is using a bitmask which will definitely exceed the memory constraint (2^50 at worst case).

The trickest part of the problem is state compressing our DP algorithm. If we can somehow reduce the memory footprint whilst also keeping the correctness intact, then a viable solution is generated. Let's take out our bitmask and try to find a way to implicitly represent that information. A common reduction in this situation is to somehow find the relationship between our current DP state parameters (in this case, strength and intellect) and the DP state parameter(s) we want to get rid of (in this case, how we can implicitly represent the missions completed so far). In fact we can see that they have a direct relationship! If we are given a particular strength and intellect we can already uniquely determine which missions can be completed, as we take all viable missions as all the points are strictly positive (always something to gain, nothing to lose).

Now our DP state becomes simply:

D(S, I) = the maximum number of missions if we can get to strength S and intellect I.
D(S, I) = 0 if the state is unreachable (not enough points).

We can proceed to pre-compute the maximum number of missions for each state as there are only 1000 * 1000 = 1 million such states. We can also pre-compute whether or not a state is possible or not. A state is impossible if we don't have enough points to cover the increase from strength 1 to S, and intellect 1 to I. Of course, this doesn't fully dictate the feasibility of a state but it's a good start. To compute the number of excess (unused) points we simply sum up all the points gained from completing the missions and subtracting S-1 and I-1 from it (as we expended S-1 strength points and I-1 intellect points to get to the current state). This calculation is done as follows:

pair<int,int> preComp[1011][1011];
...
   for (int i = 0; i <= 1000; i++) {
      for (int j = 0; j <= 1000; j++) {
         int pointsGained = 0, missions = 0;
         for (int k = 0; k < strength.size(); k++) {
            if (strength[k] <= i || intellect[k] <= j) {
               pointsGained += points[k];
               missions++;
            }
         }
         int extraPoints = pointsGained - i - j + 2;
         // extraPoints < 0 --> inaccessible state set to 0 missions
         // the pair is (excess points, number of missions completed)
         preComp[i][j] = make_pair(extraPoints, extraPoints < 0 ? 0 : missions);
      }
   }
...

Next, we need to determine feasibility from our original DP state (1,1) - which is the strength and intellect we start with. We recursively call the next DP state if we have unused points by either deciding to upgrade our strength by 1 or our intellect by 1. Note the number of unique states is only 1 million so this should run in time. Combining this with a caching mechanism (i.e. memoisation) we come up with our final solution:

class StrengthOrIntellect {
public:
   int numberOfMissions(vector <int>, vector <int>, vector <int>);
};

pair<int,int> preComp[1011][1011];
int memo[1011][1011];

int func(int strength, int intellect) {
   // seen it before (caching mechanism)
   if (memo[strength][intellect] != -1) return memo[strength][intellect];
   memo[strength][intellect] = preComp[strength][intellect].second;
   int extra = preComp[strength][intellect].first;
   // if there are unused points, recurse on them otherwise the maximum
   // is simply just the number of missions we have obtained so far
   return memo[strength][intellect] >?= extra <= 0 ? memo[strength]
      [intellect] : max(func(strength+1, intellect), func(strength, intellect+1));
}

int StrengthOrIntellect::numberOfMissions(vector <int> strength, vector <int> 
      intellect, vector <int> points) {
   int res = 0;
   for (int i = 0; i <= 1000; i++) {
      for (int j = 0; j <= 1000; j++) {
         int pointsGained = 0, missions = 0;
         for (int k = 0; k < strength.size(); k++) {
            if (strength[k] <= i || intellect[k] <= j) {
               pointsGained += points[k];
               missions++;
            }
         }
         int extraPoints = pointsGained - i - j + 2;
         // extraPoints < 0 --> inaccessible state set to 0 missions
         preComp[i][j] = make_pair(extraPoints, extraPoints < 0 ? 0 : missions);
      }
   }
   memset(memo,-1,sizeof(memo));
   return res = func(1, 1);
}