PROBLEM LINK:Author: Sarvesh Mahajan DIFFICULTY:MEDIUM . PREREQUISITES:DP, Bitmasking PROBLEM:Given an array of strings find the number of pairs of strings such that their concatenation contains first 20 characters of English alphabet. QUICK EXPLANATION:Represent each string as a bitmask , where i th bit is set if the ith character is present in the string. The problem reduces to finding the number of pairs in the array such that their bitwise OR is pow(2,20)1. This can be solved by a dynamic programming where dp[i] represents the number of supermasks of i. There are numerous ways to create the transitions for this dynamic programming. EXPLANATION:Notice that the only piece of information we require from a string is to find for each character if it is present in the string or not. Therefore one can imagine representing the string as a binary array where index ‘i’ in the array tells if the ith character is present in the string or not. A more compact and efficient representation of the same can be achieved by storing it as an integer bitmask,where ith bit corresponds to ith index in the binary array. So what we get is an array of integers corresponding to the strings in the input. The operation of concatenating two strings just reduces to applying a bitwise OR operation on the bitmask representation of the corresponding strings. Notice that a string will be super string if all the values in its bitmask representation are 1. That is its integer value is exactly pow(2,20)1.Lets call this value X. So now the problem is reduced to find the number of pairs in the array whose bitwise OR is equal to X. Note that the brute force approach two iterate over all pairs in O(n^2) , so we need something faster. If for each element we know the count of the number of elements with which this element has a bitwise OR of X, then we are done. But when will an element(e) have a bitwise OR of X with another element ? When the other element is a supermask of (Xe) . Here by supermask(a) , I mean a bitmask which contains all the 1 bits of a and the 0 bits of a are either 0 or 1 in the bitmask. Calculating the number of supermasks in the array: Let us say that we have calculated the quantity for all the numbers from X …. i+1. How do we calculate the quantity for i?
Let us represent the ith bitmask by x0 x1 x2 ..xk3...xk2…xk... xm. So finally dp[i]=dp[ibit(i,k)]+dp2[ibit(i,k1)][1]+dp2[i(bit(i,k2)][2] …. ALTERNATIVE SOLUTION:There exists a beautiful divide and conquer solution for calculating the dp array defined above. Define f(x,y) as the solution when we update dp counts only from masks in the range x to y. Then by calculating f(x,(x+y)/2) and f((x+y)/2+1,y), f(x,y) can be calculated easily. Can you think how ? AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here
This question is marked "community wiki".
asked 07 Mar '16, 22:58

Can you explain the approach used in this solution answered 10 Mar '16, 22:09
Hi, let f(i,k) represent the number of sub masks of i in which the leftmost(from MSB) 20k bits are same as that in i. Think of how you would make a recurrence for this. If the kth bit is 0: f(i,k) = f(i,k1) [ since no additional sub masks are added] else f(i,k) = f(i,k1)+f(ibit(k),k) [ This step adds all sub masks in which kth bit is 0 , bits to left of k are same as that in i] cnt array in this solution stores this function. Note that this is similar in essence to the dp2 array defined above.
(14 Mar '16, 18:41)

I applied the technique as mentioned in the editorial to calculate the supermasks of each num in 0 to 2^201. But getting WA on submission! https://www.codechef.com/viewsolution/14274056 Can anyone give me a test case where I would get wrong? answered 18 Jun '17, 10:35

How to solve this question if string is consist of digits between (09) and we have to find the pairs which contains all the digits from 09?? answered 28 Jan '18, 17:47
