TC SRM387 D2 1000 (MarblesRegroupingHard)

The problem statement can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=8538

There are two major approaches to solve this problem. But first, let's start with breaking down the problem, it asks us to arrange a set of jumbled up marbles into a correct box configuration. We can try a greedy strategy in which we heuristically move coloured marbles to boxes in which they have the most presence, aiming to reduce the number of moves. However it was rather easy to construct a counter-case towards this strategy. So we are faced with either doing a smart enumeration or try to reduce it towards a graph matching-like problem and hope that a standard graph algorithm solves it.

To try to reduce it to a matching algorithm we attempt to divide it into a bipartite graph. The obvious choice is colours on one side and boxes on the other side. Now we need to give a relationship between the two disjoint subsets - again, pretty obvious: the cost associated with moving the colour into a specific box. Hence we now have a weighted bipartite graph in which we need to match for minimum cost. Voila! The standard hungarian algorithm and/or minimum cost flow solves this perfectly. However, given the fact that we may not have an implementation (or even know of the algorithms) we can try and do some smart enumeration.

Enter dynamic programming (again), and it's pretty similar to SRM 444 D1 500. If we traverse the boxes and gradually expand our set of available boxes whilst keeping track of the colours we have used, we can effectively DP on this state (as it contains both the essential information to optimally decide options as well as being compact enough to be stored within the memory limit of 64MB). To keep track of the colours we simply keep a bitmask and since the maximum number of colours in the worst case is only 14, this means a worst-case space complexity of O( B * 2 ^ C ) = 50 * 16384 = 819200 (under 1MB).

As with all DP problems we then define the recurrence relation. To do this we simply consider a set of possible and valid decisions we can make at a specific DP state.

1. Skip the box (don't put any marbles into the box)
2. Assign colour i into the box (also ensuring we haven't used colour i yet due to the constraints of the problem - a simple bitwise-AND operation with the bitmask can check this)

Using these two decisions we get:

F(idx,mask) = max { F(idx+1,mask), F(idx+1,mask | (1 << colour)) + cost(idx,colour) }

We define cost(idx,colour) as the cost of moving "colour" coloured marbles into box idx. This is simple to calculate, we just need to keep track of the total number of marbles associated with that colour for all the boxes and move all those marbles except the ones that are already in box idx to that box. We define cost(idx,colour) as #Colour-Coloured Marbles - box[idx][colour].

Not forgetting base cases, an invalid configuration is when it reaches the end of the boxes and it still hasn't used up all the colours. Hackishly you can just return a value of (pseudo) "infinity" for this situation. Otherwise you return a value of 0 (no more additional costs/penalties associated - i.e. a valid configuration).

My implementation in the practice room follows (using the ideas above):

#define INF 1<<20

int memo[51][1<<15];
int sz; int numCol;
vector<vector<int> > vec;
vector<int> totalColors;

int func(int idx, int mask) {
  int res = 0;
  if (idx == sz) {
     return mask == (1 << numCol)-1 ? 0 : INF;
  }
  if (memo[idx][mask] != -1) return memo[idx][mask];
  res = func(idx+1, mask);
  // assign colour
  for (int i = 0; i < numCol; i++) {
     if (mask & (1 << i)) {
         // taken
         continue;
     }
     res <?= func(idx+1, mask | (1 << i)) +
          (totalColors[i] - vec[idx][i]);
  }
  return memo[idx][mask] = res;
}

int MarblesRegroupingHard::minMoves(vector <string> boxes) {
  int res = 0;
  totalColors = vector<int>(14,0);
  for (int i = 0; i < boxes.size(); i++) {
     istringstream iss(boxes[i]);
     vec.push_back(vector<int>());
     int val;
     int idxC = 0;
     while (iss >> val) {
         vec[i].push_back(val);
         totalColors[idxC++] += val;
     }
     numCol = idxC;
  }
  memset(memo,-1,sizeof(memo));
  sz = boxes.size();
  return res = func(0, 0);
}