a bit of dp and bit manipulation: SPOJ - ASSIGN

Problem Statement:
SPOJ - ASSIGN

Summary:
There are N students and N assignments, and an NxN matrix where cell[i,j] = 1 if student i likes assignment j, and 0 otherwise. Find the number of ways of assigning N assignments which satisfies all students' preference. (N <= 20)

Solution:
In recursive terms, this is mostly a straight forward DP problem with the following relationship:
S(k, bitmask) = the number of ways of assigning assignments to students k .. N, with bitmask representing the assignments that are already assigned to students 1 .. k-1. Then,
S(k, bitmask) = sum { S(k+1, bitmask with bit i switched ON if student k likes assignment i) }

However, the recursive DP does not cut for the time limit, while the bottom-up DP can. Starting from all bits turned ON in bitmask, we proceed down to 0 by decreasing bitmask with 1 each time. For each particular bitmask, we compute the number of bits turned ON, which tells us which student we are at.

/* Bottom-up implementation 

As we go decrement b, all values dp[NMAX-1] .. dp[b+1] are already computed

Hence they can be used to calculate dp[b].

*/

cin >> N;
for(int i=0;i<N;++i){
    for(int j=0;j<N;++j){
        cin >> like[i][j];
    }
}
int NMAX = (1<<N);
for(int i=0;i<NMAX;++i) {
    dp[i] = 0;
}
dp[NMAX-1] = 1;
for(int b=NMAX-1;b>=0; --b) {
    int n = b;
    int k = 0;
    while(n){
        k += (n&1);
        n /= 2;
    }
    for(int i=0;i<N;++i){
        if(like[k][i] && !(b & (1<<i))){
            dp[b] += dp[b | (1<<i)];

        }
    }
}
cout << dp[0] << endl;