Help needed in BSPDP0 problem

Link to problem :https://www.codechef.com/BGS12020/problems/BSPDP0
My logic: I create a 8 bit mask for each array. 8 because there are only 8 prime numbers till 20. This mask represents whether or not a prime number is present in the array or not(bit is set if present else it is not set).
Total number of ways of choosing triplet is nc3. So I find no of triplets which do not satisfy the given condition and then subtract them from the total number of ways of choosing. Let’s say ith array, jth array, kth array do not satisfy the given condition, then (maski & maskj & maskk)=0. so i need to find such triplets whose bitwise and is 0. I can use brute force to calculate such triplets. The number of distinct masks can at max be 256( mask value ranges from 0 to 255).
Link to my code: https://www.codechef.com/viewsolution/35313978

2 Likes

I think you’re close. And I absolutely love your explanation of your logic… really wish more people would do that, even if they aren’t as elaborate as you were.

An issue you have is that it may be possible that you have an invalid triplet when all three of the masks are 0, or when two masks are the same, but you won’t count those. You can handle the first case by just adding \binom{cnt[0]}{3} to ans.

The second case, where two masks are the same but the total mask is still 0, is slightly more complicated. You can handle that by looping variables i, j from 0 to 255 (inclusive). i represents the mask that has two occurrences, j represents the other mask. Then, when i \land j = 0 (\land = bitwise and), there are exactly \binom{cnt[i]}{2} \cdot cnt[j] ways to get that set of three masks.

Example test for case 1 (answer is 0):

3 1
4
4
4

Example test for case 2 (answer is 0):

3 1
2
2
3

Example test for both cases at once (answer is also 0, I think)

6 1
2
2
3
4
4
4
1 Like

Thanks for your help. It worked.
I was wondering if my logic was absolutely wrong because I saw a few submissions and they were doing something completely different. Glad to know that I was at least close to solving this problem. This problem seemed to be way above my level at first glance.