I was solving this problem on codechef.
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.
EDIT: I can't read and wrote the solution for the much easier XOR case. So here's something else:
There was a blog post like a week ago with a trick related to putting a hierarchy in sub-masks. This should help because for each a in the array you're looking to count all numbers inside x which contain x & not(a). I can't find it but the gist of the idea is as follows.
Consider the mask 1101101. We can impose a hierarchy on the submasks by considering the first 1, and considering submasks that have the first 1 and submasks that don't. So submasks of 0101101 and submasks of 1101101 with a leading 1. This forms a DAG between masks and can be used to count a node by adding the children.
OR != XOR.
The blog post you are talking about is this SOS (Sum Over Subsets) DP. We can solve the question using the concept mentioned in the blog which you described in the comment though my question was related to OR not XOR but the technique is still same (with little modification) So, thank you. :-)
That's the one! Glad you found it and it helped.
This problem can be solved in a technique similar to one the mentioned in this blog.
Let's denote Y = 220 - 1 So what we can do is for every element of array let's say ai, we calculate Y xor ai. Now, in our original array, we have to find the total numbers of element for which Y xor ai is a submask [subset], which is exactly what's mentioned in the blog. So, you'll create a new array b[], such that each bi = ai xor Y. You'll calculate an array d[] in a similar way as mentioned and then for each ai add d[ai] to the answer. Take care of the fact that ai OR ai can also be = Y if ai = Y.
At all, Please Stop downvoting itu's comment, at least he's trying to help( though I'm not able to get the concept till now).It demoralizes one to help others and thus has negative impact on the whole community.One may be right or wrong( and that's fine!!), you can tell him about that by replying to his comment.
Also, please fix that negative count(on itu's comment), I request you all .
Update--> The technique mentioned by itu is correct he just wrote XOR n place of OR.If anyone has doubt, give a read to SOS DP blog mentioned in other comment by me.
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
what is supermask can you give one example ??
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.