I am attempting the ASSIGN problem on spoj and I googled for a appropriate solution and saw that they were using the dp with bit masking but I didn’t understand. So could anyone just tell me how to solve this problem by bitmasking I have already google it up so please anyone could just explain it.

Thank in advance

Hi japoorv,

if you have trouble with DP + Bitmasks, then first don’t think of bitmasks. Instead, think of sets!

We need to think of a function, which we later can memorize with dynamic programming. Here, the very good approach is to use the function f(n, s), which calculates the number of combinations of the first n students and if the only available subjects left are in the set s. To calculate the wanted result, we must call f(n, {0,1,…,n-1}), since we are considering **all** n students and the available subjects are **all** subjects initially.

The recurrence of f(n, s) is easy to derive, but don’t worry, I will explain it to you.

We know by the rules, that each student must be assigned to **one** subject. So let us consider by convenience the nth student in the recurrence f(n, s). He **must** take one of the subjects in the available set s. So we need to consider **all** combinations of it. So for each still available subject e (element of s), the nth student can be assigned with e. That’s why, after assigning student n with e, we have n - 1 students left and the available subjects are s without e. But how many combinations are there with n - 1 students and (s without e) available subjects? Exactly, it is f(n - 1, s without e).

The recurrence: f(n, s) = sum of all f(n - 1, s without e) for each element e in s

The base case: f(0, {}) = 1

Hopefully you understand the recursion, otherwise you will have trouble doing DP with bitmasks. Because the bitmask technique is only (as the name says) a technique we use to speedup our implementations. We could even use std::vector to represent our set s, but this turns out to be unfeasible. A 4 byte integer with 32 bits is far more efficient to represent the set s.

By the way, if you fully understood the recursion, then you should realize, that a valid state (n, s) has the property n = |s|, in other words, the number of students left n is always equal to the number of available subjects left. So we can represent f(n, s) with only f(s)! That’s why dynamic programming is funny

Thats good I understood most of it but just the last line hie is f(n, s) =f(s) please explain this.

Thanks buddy.

Glad you understood most of it. The states (n, s) where n != |s| are not valid states. This is because of the fact, that n is always equal to |s|. If we have the state (s), we can derive n, by saying n := s. This is a huge improvement for the memory and for the time limit. Imagine you are saving those states in a 2D array. Then you’d require O(n * 2^n) memory, but with the new improved state, we only need O(2^n) memory.

would the following be a wrong dp state?

dp[i][j]=# ways to assign first j topics to kth student if the kth bit in i is set

foe example,

dp[26][3]=dp[11010][3] means that only the 1st 2nd and 3rd student have been assigned some topics out of the first 3 topics