Dynamic programming bit masking

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 :slight_smile:

26 Likes

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