Help for state transitions in dp+bitmask

general
, ,
1

I am trying to understand dp with bitmasks now, I got most of the trick but I don’t yet understand the nitty gritty of the state transition. There is excellent explanation in this thread The example is ASSIGN problem from spoj. I do understand how the recurrence is derived f(n, s) must be the sum of all f(n-1, s) where e(Assigned to nth student) should not be a part of the combination. However, what I do not get is, the final dp state, i.e

dp[i] = dp[i] + dp[i & ~(1 << k)];

I understand the second operand in RHS, it is the assignment except the ‘e’ in s. The first operand got me real confused. Why is it being added? How is it calculated before? Can anybody give me the statement of this relation term by term in an English Sentence so that I can read what exactly this recurrence should sound like? The implementation of the above recurrence is in this thread Much thanks!

1 Like
2

The code we have is this.

dp[0] = 1;
for(i = 1; i < (1 << n); i++){
  j = 0;
  dp[i] = 0;
  for(k = 0; k < n; k++){
     j += ison(i, k); 
  }
  for(k = 0; k < n; k++){   // main loop
     if(a[j - 1][k] && ison(i, k)){
        dp[i] += dp[i & ~(1 << k)];
     }
  }
}

Let’s try to understand what each entity means.
n is the number of subjects and students.
i represents a set of subjects. For example i=13=1101 means i is the set of subjects {0,2,3}.
j is the cardinality of set i. So for i=13, j=3. This also means that the 3 subjects in i have been assigned to the first 3 students.
k simply serves as an index for the subjects.
dp[i] is the number of ways the subjects in set i can be assigned to the first j students such that each student gets a subject he likes. Note that this may be 0 if no such assignment is possible.

Now let’s go over the main loop, the logic of which is as follows.

for each subject k in i:                      |   if(ison(i, k)) ensures only subjects in
                                              |    set i are considered
    if jth student likes k:                   |   if(a[j-1][k]) ensures jth student only
                                              |    gets a subject he likes
        dp[i] = dp[i] + dp[i with k removed]  |   dp[i] += dp[i & ~(1 << k)] does that

In the end dp[2^n-1] is the number of ways the full set of n subjects can assigned to n students in a valid manner. I hope this clarifies the logic somewhat. Feel free to ask if I missed some part that you still don’t get :slight_smile:

3 Likes
3

Hey @abhidoeslinux, dp[0] is 1 because there is just one way to assign 0 subjects to 0 students… no one gets anything! That is a valid way. The reasoning is similar to the number of ways of ordering 0 objects [0!=1] or number of ways of choosing 0 objects from n objects [{n \choose 0}=1].

About the recurrence f(n, s) = sum of f(n-1, s except e) for each e, this relation doesn’t apply perfectly to this particular problem. You can consider the value j as n in this statement, then it makes sense. But since j is just the cardinality of set s (named i in the code), it is an intrinsic property of s. Thus our recurrence is just a function of one variable s.

If you want to think of the recurrence in simple English, I suppose that would be “the number of ways to assign the j subjects in the set i to the first j students equals the sum of the ways to assign j-1 subjects of the set i with subject k removed to the first j-1 students, for each subject k in set i that the j^{th} student likes”.

1 Like
4

Nice explanation!!

5

Thanks for this!! :slight_smile: I understand most of it, however, the statement “dp[i] may be zero if no such assignment is possible”. Doesn’t it contradict with the base case dp[0] = 1? If there are no subjects in the set, zero subjects can be assigned to first zero ways must be zero if I understand it rightly? Also, if you can help me co relate dp[i] = dp[i] + dp[i with k removed] with the recurrence relation f(n, s) = sum of f(n-1, s except e) for each e. How do I read this in simple English? Thanks for your patience and help :slight_smile: