PROBLEM LINK -
Author and Editoriallist - AmirRezaPoorAkhavan
Tester - MohammadSina Pakseresht
Second Tester - Shayan CheshmJahan
DIFFICULTY –
PREREQUISITES –
Dynamic-programming, bitmasks.
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];
Proof: Read SoS Dynamic Programming solution section in the link above.
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.
