Bit Masking and DP | Part 1 | Assign Caps to Persons

Hello guys, welcome back to “code with asharam”. This has been the longest break we ever had. I had kickstart in this week and I also posted the solutions of the kickstart which led to such a long delay in posting this tutorial. But don’t worry, from now on, I will try my best to keep both this blog and my YouTube channel in sync. So in this post, I am going to introduce to the application of Bit Masking and DP combined. If at any moment it feels like that things are going over your head, then, I advice to go through all the last DP tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment or send me a mail. I will answer your query as soon as possible. So, without any further delay, let’s take a dive into deep oceans of Bit Masking and DP.

Assign Caps to Persons

There are 100 different types of caps each having a unique id from 1 to 100. Also, there are n<=10 persons each having a collection of a variable number of caps. One day all of these persons decide to go in a party wearing a cap but to look unique they decided that none of them will wear the same type of cap. So, count the total number of arrangements or ways such that none of them is wearing the same type of cap. Output number of ways % (109+7) as output might be large.
Disclaimer:The problem statement has been taken from geeksforgeeks.
Pre-requisite: Dynamic Programming and Introduction to Bit Masking

Brute force solution

If I speak in plain English, then, the brute force approach of this problem can be stated easily. Actually the problem itself is telling you to approach in brute force manner. We have to find total number of ways of assigning caps to persons which will be large and that is why even n is so small. Therefore, you can expect the time complexity of the solution of this problem to be exponential. So, let’s see the approach:
For ith cap, we have 2 choices – either don’t give it to anyone or give it to one of the person who have this cap in his/her collection and have not been assigned any cap from 1 to i-1.
You might note that we don’t need to compute anything if all persons have been assigned caps. So, this will act as our base case.

  1. caps[i][j] is true if jth person has ith cap.
  2. check[i] is true if ith person have not been assigned any cap.
  3. ways(check, i) returns the number of ways of assigning ith cap provided that we already have considered 1st i-1 caps and check is defined in last point.
Algorithm
define ways(check, i):
      0 if i>100 as caps are till 100 only,
      1 if check consist of only true elements,
      dontAssign = ways(check, i+1)  // case for not assigning caps
      Assign = 0
      for j in [0, n):
            if (check[j] and caps[i][j]):
                 check[j] = true   
                 Assign += ways(check, i+1)
                 checkp[j] = false   // revert back to original state
      return Assign+dontAssign

finalAnswer = ways(check, 1) and check have all the false elements                 

Now, try to construct the recursion tree of this algorithm like we used to do in dynamic programming problems. After doing that, you will see that there are many function calls with same arguments. This means that there is overlapping of sub problems. But now comes the problem! In traditional dynamic programming problems, the arguments used to be integers which can be easily represented by integer arrays. But in this case, one of our argument is an array and to represent the argument of this function by an array, we will need (length of check + 1) dimensional array which is really inefficient. This is where Bit Masking and DP comes into the picture. Let’s see how?

Bit Masking and DP solution

You know that we are using check array to represent whether ith person has been assigned a cap or not. Now, I told you in Introduction to Bit Masking that you can also use integers to represent the arrays whose elements can only attain binary values. Hence, we can replace check array with the integer having n bits. Now, converting our recursive function to a dynamic programming solution is a cakewalk. We can simply create an array of dimension 2nX100 to store the values of all distinct function calls possible.
So, we have finished writing algorithm for our problem. Now, let’s write a beautiful code for it.

Code

#include <bits/stdc++.h>
using namespace std;

const int m = 1e9+7;

int n, dp[1025][101];
vector<int> caps[101];

int cnt(int mask, int i) {
    
    if (mask == (1<<n)-1) return 1;
    
    if (i>100) return 0;
    
    if (dp[mask][i] != -1) return dp[mask][i];
    
    int ans = cnt(mask, i+1);
    
    for (int j=0; j<caps[i].size(); j++) {
        
        if (!(mask & (1 << caps[i][j]))) {
            ans += cnt(mask | (1 << caps[i][j]), i+1);
            ans %= m;
        }
    }
    
    return dp[mask][i] = ans;
}
   


int main() {
    
    memset(dp, -1, sizeof(dp));
    n = 3;
    caps[1].push_back(0);
    caps[2].push_back(1);
    caps[5].push_back(0);
    caps[5].push_back(2);
    caps[100].push_back(0);
    caps[100].push_back(2);
    
    cout << cnt(0, 1) << endl;
        // output is 4
        return 0;
}

So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve Sherlock and coprime subset.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: