TC SRM 487 D1-500 KiwiJuice

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

class KiwiJuice {
public:
   int theProfit(int, vector <int>, vector <int>);
};

int dp[51][1<<16];
vector<int> data;
vector<int> price;
int _C;

// f(current volume of the special bottle, bitmask of the used bottles)
int f(int i, int mask) {
   // caching mechanism
   if (dp[i][mask] != -1) return dp[i][mask];
   // base case
   if (mask+1 == (1 << (data.size()))-1) {
      return price[i];
   }
   int res = 0;
   for (int j = 1; j < data.size(); j++) {
      if (mask & (1 << j)) continue;   // already used
      // the next bottle to process
      int next = data[j];
      int d1 = 0;
      if (i + next >= _C) {
         // one of the bottles is full, the other is i+next-_C volume
         d1 = price[_C] + f(i+next-_C, mask | (1 << j));
      } else {
         // change to i + next (and used up the empty for bottle[j])
         d1 = price[0] + f(i+next, mask | (1 << j));
      }
      // don't add more to our current bottle
      // we swap with bottle j and "use" up our bottle
      int d2 = f(next, mask | (1 << j)) + price[i];
      
      // take the maximum of the decision branches
      res >?= max(d1,d2);
   }
   return dp[i][mask] = res;
}

int KiwiJuice::theProfit(int C, vector <int> bottles, vector <int> prices) {
   price = prices;
   int res = 0;
   _C = C;
   memset(dp,-1,sizeof(dp));
   data = bottles;
   return res = f(data[0],0);   // arbitrarily assign bottle 0 to be our special bottle
}

SPOJ - Assignments (ASSIGN)

URL: http://www.spoj.pl/problems/ASSIGN/
Category: Dynamic Programming, Bit Manipulation

The problem is quite simple: to calculate the number of different assignments of n topics to n students provided that every student gets exactly 1 topic that he likes. Each student likes different topics which is given in the format of a matrix. The essence of the problem lies in optimisation, a brute force algorithm will clearly time out if that isn't already evident. As a note, the maximum number of assignments for a 20x20 (filled with 1's) matrix is a massive 2,432,902,008,176,640,000. Since we are enumerating we can easily eliminate greedy as a design approach. Naturally we turn to dynamic programming to somehow reduce the running time to an acceptable amount.

As with all dynamic programming problems, we first define the state. The most natural and obvious state is:

D(s,u) = amount of ways to assign up to student s with a bitmask of subjects u used.

The space complexity of this DP state is O(N * 2^N). However, a observation allows us to reduce the memory footprint by a factor of N, giving a complexity of O(2^N). How does this work? The unique property of the problem is that the number of students and subjects are the same, so we can deduce that when we are up to student V, there are also exactly V bits set in the bitmask. Hence, we can simply just use the bitmask to determine which student we are up to!

Now let's define the recurrence relation:

F(u) = sum of all i { F(u | (1 << i) } where student count_of_bits(u) likes subject i

The base case is,

F((1 << total_students)-1) = 1

Note we have done something implicit. That is, we do not define the base case for where we have "left over" subjects that weren't assign to a student - this is implicitly handled by our looping.

We then code a memoised solution using the recurrence above:

long long memo[1<<20];

int count_bits(int n) {
   int r = 0;
   while (n > 0) { r += (n&1); n >>= 1; }
   return r;
}

long long func(int topicMask) {
   int idx = count_bits(topicMask);
   if (idx >= size) {
      if (topicMask != (1 << size)-1) return 0;
      return 1;
   }
   if (memo[topicMask] != -1) return memo[topicMask];
   long long res = 0;
   for (int i = 0; i < size; i++) {
      if (adjmat[idx][i] == 0 || topicMask & (1 << i)) {
         continue;
      }
      res += func(topicMask | (1 << i));
   }
   return memo[topicMask] = res;
}

Unfortunately, this times out in SPOJ, i.e. it exceeds over 20 seconds for all test cases. This is where bottom-up dynamic programming shines, given that our algorithm is probably close to the time limit (you can check by running on your own machine and noting the speed - if it's quite fast but times out in SPOJ, you are within a constant time factor of passing). Now turning it into a bottom-up dynamic programming is a bit more tricky than usual. The problem lies with the order on which to evaluate.

If we set the same base case as before with,

F((1 << total_students)-1) = 1

We need to somehow traverse backwards whilst also ensuring that we have computed all DP states that are one bit away from the one we are calculating. Turns out due to binary number representation, traversing from (1 << total_students)-1 to 0 is sufficient. This is a rather easy proof and hence left to the exercise of the reader (just list them out for 4-bit numbers and you should see the connection).

The implementation is detailed below:

int adjmat[21][21];
int size;
long long memo[1<<20];

int count_bits(int n) {
   int r = 0;
   while (n > 0) { r += (n&1); n >>= 1; }
   return r;
}

int main() {
   memset(adjmat,0,sizeof(adjmat));
   ios_base::sync_with_stdio(false);
   int nT;
   cin >> nT;
   while (nT-- && cin >> size) {
      memset(adjmat,0,sizeof(adjmat));
      memset(memo,0,sizeof(memo));
      for (int i = 0; i < size; i++) {
         for (int j = 0; j < size; j++) {
            int val; cin >> val;
            adjmat[i][j] = val;
         }
      }
      memo[(1<<size)-1] = 1;
      for (int j = (1 << size)-1; j >= 0; j--) {
         int idx = count_bits(j);
         for (int k = 0; k < size; k++) {
            if (adjmat[idx][k] == 0 || (j & (1 << k))) continue;
            memo[j] += memo[j | (1 << k)];
         }
      }
      cout << memo[0] << "\n";
   }
   return 0;
}

We can shave off some extra time by using a constant time bit counting algorithm (you can google it):

#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int adjmat[21][21];
int size;
long long memo[1<<20];

unsigned numbits(unsigned i)
{
    const unsigned MASK1  = 0x55555555;
    const unsigned MASK2  = 0x33333333;
    const unsigned MASK4  = 0x0f0f0f0f;
    const unsigned MASK8  = 0x00ff00ff;
    const unsigned MASK16 = 0x0000ffff;

    i = (i&MASK1 ) + (i>>1 &MASK1 );
    i = (i&MASK2 ) + (i>>2 &MASK2 );
    i = (i&MASK4 ) + (i>>4 &MASK4 );
    i = (i&MASK8 ) + (i>>8 &MASK8 );
    i = (i&MASK16) + (i>>16&MASK16);

    return i;
}

int main() {
   memset(adjmat,0,sizeof(adjmat));
   ios_base::sync_with_stdio(false);
   int nT;
   cin >> nT;
   while (nT-- && cin >> size) {
      memset(adjmat,0,sizeof(adjmat));
      memset(memo,0,sizeof(memo));
      for (int i = 0; i < size; i++) {
         for (int j = 0; j < size; j++) {
            int val; cin >> val;
            adjmat[i][j] = val;
         }
      }
      memo[(1<<size)-1] = 1;
      for (int j = (1 << size)-1; j >= 0; j--) {
         int idx = numbits(j);
         for (int k = 0; k < size; k++) {
            if (adjmat[idx][k] == 0 || (j & (1 << k))) continue;
            memo[j] += memo[j | (1 << k)];
         }
      }
      cout << memo[0] << "\n";
   }
   return 0;
}

TC TCO06 Round 1 D1 350 (SeparateConnections)

Category: Dynamic Programming, Matching in a General Graph
URL: http://www.topcoder.com/stat?c=problem_statement&pm=6095

This problem just asks us to find the maximum number of matches in a general graph (should be a straightforward reduction given the problem constraints). The most efficient way to solve this problem is to use a maximum matching algorithm (like Edmond's). However, this is not straightforward to code and certainly not required for a 350 pointer problem. Given the constraints, one easy way to implement a maximum matching algorithm is to use dynamic programming. We will be using a bitmask to efficiently keep track of the nodes that have already been matched so far.

For those new to bitmasks, here is a very short tutorial on it. As you may know, all decimal integer numbers (base 10) have a binary representation form (base 2). As a result, each bit inside a binary representation can represent up to 1-bit of information (duh). Besides representing numbers we can use each of these bits (0 or 1) as useful book-keeping information - in our case (and in many cases) we use them to mark whether or not we have visited or used a particular resource. So for example, the bit representation 01100 could mean we have used resource 2 and 3 (0-based index). Note that we go from left to right due to the fact that the left-most bit is also the most significant bit (MSB). This bit representation (01100) is simply known as 2^3 + 2^2 = 14 in decimal. Expanding on this, let's say in our problem we have used node 1, node 4 and node 5. This is represented as 2^5 + 2^4 + 2^1 = 32 + 16 + 2 = 50. There are several important bit operations we can use to manipulate and query the bits:

For starters, to get a '1' in the n-th position from the right (remember 0-based index) - you use the shift left operator '<<'. For example, 1 << 5 yields a bit representation equivalent to 0010 0000 (32).

To set a bit, we use the bitwise-OR operator denoted as '|'. The bitwise-OR operator works by applying the OR operation to each of the corresponding bits between two numbers. The OR operation is defined as:

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

For example to set the 5th bit (again 0-index) from the right, we first use the shift left operator to yield the correct number (i.e. 1 << 5). Let's say the bitmask before the operation is defined as 0100 0010 (68). Then applying 1 << 5 which has a representation of 0010 0000 (32) yields:

0100 0010 (68) OR 0010 0000 (32) Equals 0110 0010 (100)

To test whether a bit is set within a bitmask, we make use of the bitwise-AND operator denoted as '&'. The AND operation is defined as:

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

We use a similar method as we did for setting a bit in a particular position, let's say we wanted to test if the 5th bit was set. We use the shift left operator to yield the correct number (i.e. 1 << 5). Then we simply apply the bitwise-AND operator to the bitmask we wanted to test. If our mask was 0110 0010 then it would return 0010 0000. However if our mask was 0100 0010, then it would return 0000 0000 as it has no bits both turned on at the same position. Thus, we can use this to test whether or not a bitmask contains a bit in a particular position, if it the result is positive after the AND operation then it is inside the bitmask, if it's zero then it isn't inside the bitmask.

There are other bitmasking techniques which won't be discussed here as they aren't used for this problem.

Back to the problem, given that there are only 18 nodes at maximum. We can easily create a bitmask that keeps track of which nodes we have currently used up (there are 2^18 = 262144 different combinations). So for the actual DP state, we can iteratively introduce more nodes to the set and choose any adjacent nodes which haven't been used so far. Therefore, the state is D(n,m) where n is the index of which node we are processing and m is the bitmask of which nodes we have already used up. Next, we need to define the recurrence relation as well as any base cases. The recurrence relation can be found by selecting from a set of valid decisions at a particular node.

The two available options are to:
- Not used the node in the maximum matching (in hopes that it increases the available nodes later on)
- Use the node along with another node which is adjacent to it (increases the number of matchings by 1 and decreases the available set)

We define the recurrence as: D(n,m) = max { 1 + D(n+1, m | (1 << k), D(n+1, m) } where k is the set of all unused nodes which are adjacent to n. Take note, we do not consider matching node n, if it's already been matched by the time we reach index n. Then applying a simple memoization we yield a working solution:

class SeparateConnections {
public:
   int howMany(vector <string>);
};

int adjmat[19][19];
int memo[19][1<<19];
int sz;

int func(int idx, int mask) {
   if (idx >= sz) return 0;
   if (memo[idx][mask] != -1) return memo[idx][mask];
   int res = 0;
   if (!(mask & (1 << idx))) {
      for (int i = idx+1; i < sz; i++) {
         if (mask & (1 << i)) continue;
         if (!adjmat[idx][i]) continue;
         res >?= 1 + func(idx+1, mask | (1 << i));
      }
   }
   res >?= func(idx+1, mask);
   return memo[idx][mask] = res;
}

int SeparateConnections::howMany(vector <string> mat) {
   int res = 0;
   for (int i = 0; i < mat.size(); i++) {
      for (int j = 0; j < mat.size(); j++) {
         if (mat[i][j] == 'Y') adjmat[i][j] = adjmat[j][i] = 1;
      }
   }
   sz = mat.size();
   memset(memo,-1,sizeof(memo));
   return res = func(0,0) * 2;
}

However, one can also use a general matching algorithm like Edmond's Blossoming/Shrinking Algorithm to solve the problem. See below for such an implementation (based on Pape and Conradt variation of Edmond's which is incorrect for a certain set of inputs, but it still passed system tests for this problem). No further explanation would be provided for this algorithm as I'll leave this for a later blog entry in which we build up our matching algorithms.

#define MAX_VERTICES 21

int adjmat[MAX_VERTICES+1][MAX_VERTICES+1];
int table[MAX_VERTICES+1][MAX_VERTICES+1];
int mate[MAX_VERTICES+1];
int level[MAX_VERTICES+1];
int grandparent[MAX_VERTICES+1];

bool checkAncestor(int currentNode, int checkNode) {
       int v = grandparent[currentNode];
       if (v < 0) return false;   // not an ancestor
       if (v == checkNode) return true; // ancestor
       return checkAncestor(v, checkNode);
}

int augment(int curNode) {
       // BFS an augmenting path
       memset(level,1,sizeof(level));
       memset(grandparent,-1,sizeof(grandparent));
       queue<int> q;
       q.push(curNode);
       level[curNode] = 0;
       while (!q.empty()) {
               int x = q.front(); q.pop();
               for (int y = 1; y <= MAX_VERTICES; y++) {
                  // not part of an edge in G or seen the odd-vertex in T
                  if (!adjmat[x][y] || !level[y]) continue;   
                  if (mate[y] == 0) {
                     // found an augmenting path
                     int next = 0;
                     while (true) {
                        mate[y] = x;
                        next = mate[x];
                        mate[x] = y;
                        if (grandparent[x] < 0) break;
                        x = grandparent[x];
                        mate[next] = x;
                        y = next;
                     }
                     return 1;
                 } else if (mate[y] != 0 && !checkAncestor(x,y) && 
                         mate[y] != x) {
                     // push the node into the alternating tree T
                     q.push(mate[y]);
                     grandparent[mate[y]] = x;
                     level[y] = 0;
                 }
               }
       }
       return 0;
}

int maxMatching() {
   int res = 0;
   memset(mate,0,sizeof(mate));    // all currently unmatched
   memset(grandparent,-1,sizeof(grandparent));
   // start at the vertex i if it's single
   while (true) {
      int v = 0;
      for (int i = 1; i < MAX_VERTICES; i++) {
         if (!mate[i]) v += augment(i);
      }
      if (v == 0) break;
      res += v;
   }
   return res;
}

int SeparateConnections::howMany(vector <string> mat) {
   for (int i = 0; i < mat.size(); i++) {
      for (int j = 0; j < mat.size(); j++) {
         if (mat[i][j] == 'Y') adjmat[i+1][j+1] = adjmat[j+1][i+1] = 1;
      }
   }
   return maxMatching() * 2;
}