# How to solve Assigment problem on SPOJ? [closed]

Problem Link - Assign .This problem is known as assignment problem.

I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to understand how to solve it but i was unsuccessful ..

• We require questions to be self-contained, so that the problem statement can be understood without having to follow an external link, and so that the question will remain understandable even if the link stops working. – D.W. Oct 28 '19 at 7:47

Let us enumerate the students $$s_1, \dots, v_n$$. Let $$A$$ be the set of students and $$B$$ the set of subjects. Moreover, let $$S_i$$ be the set of subjects the student $$s_i$$ likes. The dynamic programming table will be $$C\left(A, 2^B\right)$$, where $$C(s_i, S)$$ says in how many ways we can assign the subjects in $$S$$ to the first $$i$$ students. Note that if $$|S| \neq i$$ we have $$C(s_i, S) = 0$$.
The recursive function is given by the formula $$C(s_i, S_i) = \sum_{p \in S \bigcap S_i} C(s_{i-1}, S\setminus {p}).$$
To implement the solution you need a loop over all the students and for each student iterate over all possible bit masks. For the student $$i$$ ignore all bitmasks with number of ones not equal to $$i$$. Now use the formula above to compute the value for each student and bitmask based on the values of previous students.
• Checking if $$M$$ contains $$k$$ by $$M \& (1<
• Adding subject $$k$$ to bitmask $$M$$ by $$M = M | (1 << k)$$
• Removing subject $$k$$ from bitmask $$M$$ by $$M = M \& (((1<.