1
$\begingroup$

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 ..

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Oct 28 '19 at 7:47
0
$\begingroup$

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.

Notes:

  • Checking if $M$ contains $k$ by $M \& (1<<k)$
  • Adding subject $k$ to bitmask $M$ by $M = M | (1 << k)$
  • Removing subject $k$ from bitmask $M$ by $M = M \& (((1<<n) - 1) - (1<<k))$.
Improve this answer
$\endgroup$