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