Блог пользователя Sammmmmmm

Автор Sammmmmmm, история, 11 месяцев назад, По-английски

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

N <= 1e5;

Ai <= 1e9

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

This problem can be solvable with trie.

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

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

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    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?

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Tysm. That's such a cool solution!

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
Rev. 5   Проголосовать: нравится -10 Проголосовать: не нравится

Just deleted my comment related to code,

I misunderstood the constraints earlier_

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

    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;
    }
    
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Read bounds...

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this is from ongoing contest

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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.

»
11 месяцев назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

code
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I find something weird.

    code1
    code2

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

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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