Number of pairs in an array whose bitwise OR is equal to X.

Revision en1, by griever, 2017-06-16 06:46:54

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.

Tags bitmasking, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English griever 2017-06-16 06:46:54 638 Initial revision (published)