O - Matching

tutorial
1

help needed.
I saw errichto video ,he used bitmask I do not know how to use bitmask in the following problem.I also wants to know when is bitmasks used in dp.

thanks in advanced

1 Like
2

A bitmask is used to store which women are already chosen.
Say there are 3 women
111 would mean all three are available.
110 would mean only the third one isn’t available, etc.
A bitmask is not much different than a boolean array.
You can alternatively just store it as a number where 111 =7 and 110=6 etc.
The main observation was you can choose an arbitrary order of men and find the way to pair them, as any allowed method Can be rearranged such that man 1 is first, man 2 is second and so on.
Now let dp[i][j] denote we have i men left and j is the bitmask for women left. Now dp[i][j]=\sum dp[i-1][j-2^w] where w denotes the index of all the women he can match with. subtracting 2^w removes that women from the bitmask, signifying that women at index w is not available. With this, we can form a recursive relation.
My commented submission

8 Likes
3

nope ,I have kept 2 of the previous problems in my to do list

4

At least all the questions till L?

5

yes I have solved all till L except dequeue.

1 Like
6

how to represent the state of the dp recursively ?
What if number of men compatible is less than number of women or vice versa.How to check if I have formed pairs of length N?

7

I’ve linked my code. It’s fairly well commented. If there is some part of my code that is not comprehensible, just ask me.

8

That we only check at the end. If after making the pairs, the last person has no pairs we return 0. If the current person does not have any pairs, we do not call the recursive function at all.

for(int i=0;i<n;i++){
        if(left & (1ll<<i)){//If the ith women is left
            if(compatibility[N-1][i]){//If the 2 are compatible
            currans+=solve(N-1,left - (1ll<<i));
            //Find the number of pairs after pairing them
            //and add all of them
            }
        }
    }

The inner solve function will only be called if there is a women left and compatible with this person. Since we initialise currans as 0, The code will return 0, if there is no women left that is compatible with this person.

9 
mod = 10**9+7
 
n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]
 
dp = [-1 for __ in range(1 << n)]
dp[0] = 1
 
 
def dfs(bit, i):
    if dp[bit] != -1:
        return dp[bit]
    else:
        tmp = 0
        for j in range(n):
            if bit & (1 << j) and a[i][j]:
                tmp += dfs(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]
 
 
print(dfs(2**n-1, 0))

This code I got from submissions of some random guy for the same problem.How can we define the state of dp in this code.What does dp[i] mean here.

10

You can alternatively do it with 1 bitmask, since the number of set bits will be the number of men left as everytime we make a pair, we remove a man and a woman. So using that you can do it in a 1d dp, but as per the constraints it wasn’t necessary and is more intuitive to use both.

3 Likes
11

Can you explain how to do this using 1d dp?
@errichto in his video does something funny with the number of set bits in the mask. I understand the usual solution, but I cannot find any explanation for this solution.
I made some observations that at the start of the i^{th} iteration of the bitmask, the loop invariant is that dp[i] has been calculated. How can we prove that dp[i+1] is correct at the end of the i^{th} iteration?

1 Like
13

For recursive function implementation with bitmasking, see my submission matching recursive implementation