# MAXOR - Ediorial

Practice

Contest

Author and Editoriallist - AmirRezaPoorAkhavan

Second Tester - Shayan CheshmJahan

DIFFICULTY

PREREQUISITES

EXPLANATION

In this problem let z = 20 and maxk = 2 ^ {20}.

Let’s prove that max(X, Y) \leq X | Y. Consider Y \leq X, so the left part of inequality is equal to X. It’s obvious that X \leq X | Y. So we have to count pairs such that max(X, Y) = X | Y.
Again consider Y \leq X, so the left part of inequality is equal to X, So max(X, Y) = X = X | Y \Rightarrow Y \in X (every true bit in Y is also true in X).
Now for each mask like M, let’s count the number of i’s, such that a_i \in M. It’s really important not to overcount here. For example, this code will overcount:


for(int i = 0; i < maxk; i++)
for(int j = 0; j < z; j++)
if(i >> j & 1)
dp[i] += dp[i ^ 1 << j];



You should use SOS (Sum over Subsets) dp trick, as mentioned here. Look, this code will work:


for(int j = 0; j < z; j++)
for(int i = 0; i < maxk; i++)
if(i >> j & 1)
dp[i] += dp[i ^ 1 << j];



Now the remaining part is easy. For each mask like M, calculate cnt_M, the number of times it occurred in A.

Now it’s simple that the answer is \sum {cnt_M \cdot (dp_M - cnt_M) + {cnt_M \choose 2} }.

Because there are dp_M - cnt_M indexes like i of the array such that a_i \in M and a_i \neq M so we should count them. In addition, there are {cnt_M \choose 2} pairs of elements of the array such that are equal to M, so we count them separately.

Time complexity: \mathcal{O}(n + z \cdot 2 ^ z)

IMPLEMENTATION -

Author’s code - here.

Tester’s code - here.

Second tester’s code - here.

9 Likes

Could you please explain the formula in the end?

I solved it using tries. It is simple with tries here is my code

I solved it using tries but now I feel it was overkill.

formula is (cntm * dp[i]) + (cntm(cntm-1)) / 2* because for a mask m
there are its cntm occurence in Array A and dp[i] is all such X which are subset of m (every true bit in m is also true in X) so number of pairs possible are cntm * dp[i] + (cntm * (cntm-1))/2

explain the formula a bit more given at the end? Thanks

@arpa, why does it give me WA if I swap the inner for loop with outer for loop in the last code snippet (SOS DP)? What is going wrong in this case?

1 Like

can someone explain me how to solve this using trie?

1 Like