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;