### griever's blog

By griever, history, 4 years ago,

I was solving this problem on codechef.

Question

Editorial

I figured out the bitmasking part (which is to reduce each string to a mask of length 20 to represent first 20 Alphabets) but I'm stuck on the part to count number of pairs with all bits set( that is they contain all characters). I'm able to come up with only O(N^2) solution and not able to understand the method(which does it in O(N)) described in the editorial.Please, if anybody can help me with that.

• +12

•  » » 4 years ago, # ^ | ← Rev. 3 →   +5 Ok, here's my explanation and I am assuming you've understood that for each bitmask B present in given input, we need to find the count of supermasks of X-B in the input array (X=2^20-1)._**So basically we need to find the supermasks of each number from 0 to X **_ __How to calculate supermasks? Let's say we need to find supermasks of B = 10101001011. We can use DP. Assume we have already calculated the supermasks of all numbers from B+1 to X and stored it in an array super[] where super[i] represents the count of supermasks of i. Now I'll explain the substructure of this DP.We observe that here we have 5 zero bits in B. And since we are counting supermasks, we know that any of these 5 bits can be set to 1. Let's set the leftmost 0 bit to 1 and add the supermasks of resulting number to super[B] --> super[B] += super[B|(1<<9)] Now let's set second 0 bit from left to 1 and add it. super[B] += super[B|(1<<7)]. However, here we have counted same value multiple times. Consider the case when supermasks of B|(1<<9) contains the supermasks of B|(1<<7) as well, after all its supermasks. So we need to calculate only unique cases and avoid the overlapping ones.** In simple terms, substructure of this would be : tot_super[B] = super[B|(1<<9)][4] + super[B|(1<<7)][3] + .... + super[B|(1<<4)][1] + tot_super[B|(1<<2)] Here super[N][k] denotes those supermasks of N where rightmost k 0 bits will necessarily remain 0 and tot_super[i] is total count of supermasks of i. So now you can have an idea that we are adding disjoint values and it's correct.Now task is to calculate super[B][j] (1<=j<=k, k=number of 0 bits in B). How? --> In our example, super[B][5] = number of supermasks where the rightmost 5 bits with 0 will remain 0 which is nothing but the count of B itself i.e. number of strings in the input with bitmask B. super[B][4] = super[B][5] + super[B|(1<<9)][4]. Think about it and you'll know why. super[B][3] = super[B][4] + super[B|(1<<7)][3] ... and so on upto super[B][1]. The last value tot_super[] is added because the rightmost 0 bit has no zero bits to it right and so we can safely add the total supermasks of B|(rightmost 0 bit). Here's my solution. Look at the code and you'll understand whatever I explained. Tell me if still any query persists
•  » » » » 20 months ago, # ^ |   0 Supermask of a bitmask is another bitmask obtained by setting a subset of 0's of original bitmask to 1 and letting the rest of string untouched. There can be numberous supermasks for a given bitmask.Example: Let B = 1001110, we have three 0's here. Let's flip the first and third zero to obtain a supermasks which is = 1101111. If we flip the first two, then we have = 1111110 and likewise we can have a total of $2^k$ number of supermasks, where k = number of zeroes in the given bit string.Note: Given bitmask itself is also a supermask.