I am not sure about N, but it must be not O(n^²) solution.
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
I am not sure about N, but it must be not O(n^²) solution.
Name |
---|
Attempt 2 Let x&y = 2^k = (100..00)2 with k zeroes. Clearly, k+1-th bit should be 1 in both x and y (a&b=1 <=> a=b=1). And clearly x and y should have no other common bits. Let's find the number of pairs for each k. First, take only those numbers with k+1-th bit set. Consider one of them as a candidate for x. If it has ones in some other positions, then y should have zeroes in those positions. This translates into following: let mask = !(x) + 2^k and find all other numbers with k+1-st bit set, that are submasks of mask. For each k, you can find this number with dp over submasks.
i couldn't get the thing "Also all other bits should be 0 in both x and y (a&b=0 <=> a=b=0)" why? if other than $$$k$$$th bit if a bit is set in atmost one of $$$x$$$ and $$$y$$$ then still their bitwise and will be power of 2.
Lol, playing smart just wakig up is not a good idea! Updated.
Now it's correct. I think it's time complexity will be O($$$bits$$$ * $$$bits$$$ * 2$$$bits$$$), where $$$bits$$$ = floor(log2($$$maxAi$$$)). Correct me if i am wrong?
what topic should i study for understanding this? dp+ bitmask right?
Sum over subset dp(called as SOS dp). Here is a nice tutorial.
a AND b = 0 implies either a or b is 0 not both My proposed solution was wrong.