Given an array of N integers. Count pairs (i, j) so that (A[i] & A[j]) = 0
N <= 1e5;
Ai <= 1e9
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Given an array of N integers. Count pairs (i, j) so that (A[i] & A[j]) = 0
N <= 1e5;
Ai <= 1e9
Name |
---|
Auto comment: topic has been updated by Sammmmmmm (previous revision, new revision, compare).
where is this problem found??? or is it just a problem you created by urself?
The problem is here https://tleoj.edu.vn/contest/026 (3rd problem)
This problem can be solvable with trie.
Can you explain it in more detail? Thanks
Do you know trie?
I know trie but not how you can solve this problem with it...
i dont think trie can solve this problem...trie always used in xor problem but not and qwq
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:.
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?
Tysm. That's such a cool solution!
You can solve it in O(N^2/word) with such constraints, but how to apply SOS dp there no clue..
Just deleted my comment related to code,
I misunderstood the constraints earlier_
can use, this function also
Read bounds...
extremely sorry for that, I though it's same as n
Sorry guys
this is from ongoing contest
No, it's not. Somebody already sent the link.
by the way,i want to ask how to solve ai & aj = k problem. may be sqrt,but i do not know how.
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.
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 thata[i] & k == k
. Replace them witha[i] & ~k
and the problem boils down with zero bitwise and.Brute force in custom invocation (c++20) on codeforces only costs 546ms.
I find something weird.
code2 costs 546ms but code1 costs 3416ms on codeforces, while both cost ~750ms on my notebook.
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))??
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
Im having trouble understanding what's going on in the code.
I'd be grateful if you can explain the approach.
Thanks!
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