Sammmmmmm's blog

Count pairs (A[i] & A[j]) = 0 but Ai <= 1e9
By Sammmmmmm, history, 17 months ago, In English

Given an array of N integers. Count pairs (i, j) so that (A[i] & A[j]) = 0

N <= 1e5;

Ai <= 1e9

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

Comments Comments (27)
| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Sammmmmmm (previous revision, new revision, compare).

→ Reply
»
17 months ago, # |
  Vote: I like it +8 Vote: I do not like it

where is this problem found??? or is it just a problem you created by urself?

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

This problem can be solvable with trie.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Can you explain it in more detail? Thanks

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Do you know trie?

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

        I know trie but not how you can solve this problem with it...

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

        i dont think trie can solve this problem...trie always used in xor problem but not and qwq

        → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

I like this problem, it has clever trick I've not seen exactly in this form. Assume numbers are < 2^30. The key is noticing that if (a[i] & a[j]) == 0 then at least one of the numbers in a valid pair must have bitcount less <= 15. Also, 30C15 ~ 1e8.

Let's split numbers into two groups, those with bitcount <= 15 in set S and those >= 15 in set T. Then from before, no pairs between elements in T will work, so we only need to count pairs in S and pairs between S and T.

For pairs in S, we are going to consider for each element in S how many other pairs in S intersect with its bitmask and subtract those. To find number of masks that intersect another mask we can use SOS dp.

For pairs between S and T, we are going to consider for each element in T how many elements are there in S only using bits in unset bits of T element. We can find number of elements within mask using SOS dp as well.

Now you may say SOS dp is too slow because it is 30 * 2^30. However, realize in both cases described above we are only iterating over masks with at most 15 bits. This means SOS dp will actually be more like 30 * 30C15 :eyes:. With a bit of constant optimization and luck something along this line will hopefully pass.

Actually I'm not confident this is right approach, it seems it will be difficult to deal with memory, if there is way better solution someone please let me know :pray:.

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Oh to deal with memory, ig why do SOS dp, for all elements you should be able to iterate over corresponding bitmasks naively. It will then be n * 2^15 and 2^15 memory.

    That seems a bit less cool tho :(. Does anyone know problem that forces technique more like I described with SOS dp?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Tysm. That's such a cool solution!

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

      You can solve it in O(N^2/word) with such constraints, but how to apply SOS dp there no clue..

      → Reply
»
17 months ago, # |
← Rev. 5   Vote: I like it -10 Vote: I do not like it

Just deleted my comment related to code,

I misunderstood the constraints earlier_

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it -18 Vote: I do not like it

    can use, this function also

    long long solve(vector<int> &contain)
{
	if(contain.size()==1)
		return 1LL*contain[0]*contain[0];
 
	vector<int> halved(contain.size()/2);
	for(int i=0;i<contain.size()/2;i++)
		halved[i]=contain[i+contain.size()/2];
	long long ans = -solve(halved);
 
	for(int i=0;i<contain.size()/2;i++)
		halved[i]+=contain[i];
	ans+=solve(halved);
 
	return ans;
}
    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Read bounds...

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      extremely sorry for that, I though it's same as n

      Sorry guys

      → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this is from ongoing contest

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    No, it's not. Somebody already sent the link.

    → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

by the way，i want to ask how to solve ai & aj = k problem. may be sqrt，but i do not know how.

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    The best I know is approach like this problem, but I think it won't fit in memory for these bounds.

    I misunderstood, for some reason I thought k bits.

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    What problem? Like in the blog, but bitwise and is k instead of 0? They are the same, that is, k = 0 is the hardest case. Otherwise you need to consider only those a[i], such that a[i] & k == k. Replace them with a[i] & ~k and the problem boils down with zero bitwise and.

    → Reply
»
17 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Brute force in custom invocation (c++20) on codeforces only costs 546ms.

code
→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I find something weird.

    code1
    code2

    code2 costs 546ms but code1 costs 3416ms on codeforces, while both cost ~750ms on my notebook.

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

      Why does this code2 not give a timeout if a for is done up to n and then another nested up to n, it would be a total of 1e10 (O(n*n))??

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

        See $$$n\leq 10^5$$$ which is a kind bound. $$$10^{10}$$$ will TLE, but stuff like $$$10^9$$$, $$$2\cdot 10^9$$$, can be accepted too. The checking part is a very simple operation so compiling optimization like vectorization and loop unrolling provided enough boost to push running time under the edge

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

    Im having trouble understanding what's going on in the code.
    I'd be grateful if you can explain the approach.
    Thanks!

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

      In his code1 and code2 he is just doing the brute force for i, for j approach but turns out the commenting happened to trigger/untrigger an optimization leading to run time discrepancy

      In the original code he is doing something smart. He splits array into blocks of 32. Then for each pair of blocks, he checks the pairs formed by choosing an element from each. As a result, for each ~32x32 comparisons his array accesses remain very close together which speeds up the program due to cache locality. But turns out this optimization wasn’t needed since the for i for j brute force approach passed as well

      → Reply