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

### 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;

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;
}
}

}

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.