Hi, I spent one day for this problem but I haven't come up with solution for this problem. Can you take a look at this problem? Thanks.
Statements:
Given an array which have $$$n \leq 10^5$$$ elements which values are $$$\leq 2^{16}$$$, count all pairs in array which differ in exactly $$$K \leq 16$$$ bits of binary representation of both the numbers.
Sample Input:
5 2
2 4 1 3 1
Sample Output:
5
Explanation: $$$(a_1, a_3); (a_1, a_2); (a_1, a_5); (a_2, a_3); (a_2, a_5)$$$
Link: https://www.spoj.com/PTIT/problems/P186PROF/ (in Vietnamese since I can't find any other links). Test case for this problem in SPOJ is weak, since I got accepted with time complexity $$$O(n \times \binom{16}{k})$$$. But this is not the intended soluton, maybe.
We can use "xor convolution" to find xor's of all pairs in the array. Now counting sum of pairs whose xor has exactly k bits set is the answer.
Since we need to count tuples with i < j it is twice the actual result for k > 0 and you probably want to handle the k=0 case separately.
With its small limits, can we have simpler algorithm? Thanks.
Aren't the original problem constraints ai<=1e4 and k<=14? If that's the case, we can have a frequency array and we can brute force the bits where the pair differ.
Time complexity <= 1e4 * (14c7) = 3.4e7 which is acceptable
Thank you, but my original problem has $$$k \leq 16$$$. I tried to found it in the Internet but I just found problem with $$$k \leq 14$$$.
My original problem is from an old OI contest (2021) in VN. Anyone who thinks I'm cheating can check the original problem here: Link ( in Vietnamese, of course :) ).
i think that will solve this: lang is c programming.
include <stdio.h>
int countBits(int x){ int count=0; while(x){ if(x&1){ count++; } x>>=1; } return count; } int countPairs(int arr[],int n,int k){ int count=0; for(int i = 0;i<n;i++){ for(int j=i+1;j<n;j++){ int diffBits=countBits(arr[i]^arr[j]); if (diffBits==k){ count++; } } } return count; } int main(){ int n,k; scanf("%d%d",&n,&k); int arr[n]; for(int i=0;i<n;i++){ scanf("%d",&arr[i]); } int count=countPairs(arr,n,k); printf("%d",count); return 0; }
TLE.
Maybe bitmask dp can help. Dp(mask)(j)(k) means the number of integers x (such that x is a part of array) such that mask and x differ in at most k bits and the first j bits (from left side) of mask and x are same.
Try to come up with transitions. I'm too sleepy right now to write the complete transitions. But zi'm pretty sure it will work :)
When you wake up tell us how you can make it
I think it will be slower than brute force.
Can you explain a bit more about your formula? Thanks.
Sir, you've been sleeping for two whole days.
Someone helps me please :(
First, you handle the case $$$k$$$ = $$$0$$$ separately.
For case $$$k$$$ > $$$0$$$, the number of pairs is simply the sum of (occurrences of $$$i$$$ in the array) * (the number of elements in the array that can be transformed into $$$i$$$ using $$$k$$$ bit flip), for all $$$i$$$. For example: $$$n = 5$$$, $$$k = 2$$$, $$$a =$$$ {$$$1, 3, 3, 4, 4$$$}. The number $$$1$$$ appear $$$1$$$ times, and there are no number that can transform into $$$1$$$ by flipping $$$2$$$ distinct bits. The number $$$3$$$ appear $$$2$$$ times, and there are the number $$$4$$$, which can transform to $$$3$$$ by flipping $$$2$$$ distinct bits, and it appear $$$2$$$ times. And the same goes for $$$4$$$. Therefore, the answer is $$$(2 * 2 + 2 * 2) / 2 = 4$$$
Now, to calculate the (occurrences of $$$i$$$ in the array), for each i, just use frequency table. To calculate (the number of elements in the array that can be transformed into $$$i$$$ using $$$k$$$ bit flip), you will use dynamic programming, call $$$dp[i][mask][j]$$$ the number of number that can transform into $$$mask$$$, changing only the first $$$i$$$ bits, and flipping exactly $$$k$$$ times. The transition is $$$dp[i][mask][j] = dp[i-1][mask][j] + dp[i-1][mask \oplus 2 ^ {i-1}][j - 1]$$$
Understandable, thank you!