### n0h0mo's blog

By n0h0mo, history, 2 months ago,

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.

• +9

 » 2 months ago, # | ← Rev. 2 →   +16 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.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 With its small limits, can we have simpler algorithm? Thanks.
•  » » » » 2 months ago, # ^ |   0 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
•  » » » » » 2 months ago, # ^ |   0 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 :) ).
»
2 months ago, # |
-21

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; }

•  » » 2 months ago, # ^ |   +10 TLE.
 » 2 months ago, # |   0 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 :)
•  » » 2 months ago, # ^ |   +15 When you wake up tell us how you can make it
•  » » » 2 months ago, # ^ |   0 I think it will be slower than brute force.
•  » » 2 months ago, # ^ |   0 Can you explain a bit more about your formula? Thanks.
•  » » 2 months ago, # ^ |   -10 Sir, you've been sleeping for two whole days.
 » 2 months ago, # |   0 Someone helps me please :(
 » 2 months ago, # | ← Rev. 2 →   0 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]$
•  » » 2 months ago, # ^ |   0 Understandable, thank you!