n0h0mo's blog

By n0h0mo, history, 19 months ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
19 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With its small limits, can we have simpler algorithm? Thanks.

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :) ).

»
19 months ago, # |
  Vote: I like it -21 Vote: I do not like it

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

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone helps me please :(

»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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]$$$