This is my first blog ( Hopefully not the last :D )
I came across this problem in a group contest that no one could solve (I couldn't solve it either, so i need help) basically all the problem is just given an positive integer n (1 <= n <= 1e5) and array a, your task is to find the number of pairs i, j (1 <= i < j <= n) such that a[i] | a[j] = a[i] or a[i] | a[j] = a[j]. Yes, that's it.
I'd be really grateful for any help. Thanks for your time.
Here is a solution: start one for loop iterating $$$i$$$ from $$$1$$$ to $$$n$$$ and then start another one iterating $$$j$$$ from $$$i + 1$$$ to $$$n$$$. The reason why we pick $$$i + 1$$$ is so that we don't pick duplicates and we don't count pairs where $$$i = j$$$. Increment your answer by $$$1$$$ if $$$a[i] | a[j] = \max(a[i], a[j])$$$.
That's O(n^2) though and n can be 1e5. Is there any constraint on the values in a? If they're small enough you could use subset dp
Just use SOS DP.
edit: previous comment was wrong, sos dp is the way to go
I can't understand it,how?
Let dp_i be number of values in the list whose bitmasks are a subset of i
Initial state: dp_i = number of times i appears in array
Iterate over i from 0 to 2^N-1 (this will traverse all subsets of i before hitting i)
For each i:
count the sum of all dp_j where j is a subset of i and the bit count of j is 1 less than i, call it c
add c*dp_i to your answer
set dp_i = dp_i + c
Are you sure you're not overcounting? I was also thinking about that initially.
Darn, I think you're right
The above approach overcounts because a single dp_i has multiple paths to superset states. For instance:
001->101->111
001->011->111
Instead, using initial state as described above and running subset dp should get you the right answer
why do i need to set dp_i to be dp_i + c?
Actually there is 1 <= a[i] <= 1e5
Instead of counting subsets which is O(3^n), why not use high-dimensional prefix sum, its O(n*2^n) right?
nvm thats just sosdp