MAXOR - Ediorial

PROBLEM LINK -

Practice

Contest

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.

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 :slight_smile:

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

@arpa can please add the time complexity of the solution.

Can you explain your solution please? I thought of tries at first but solved using SOS DP anyway in the end :confused:

btw what is the time complexity for this question using tries ??? I dont think it will pass if the test cases are strict

i used 5 dfs on tries.1: to get count of element which are subset of new element. 2: to get count of elements of which new element is subset. 3: to get count of elements of same size as new element but less (i.e. 0 at at least one position or 0 w.r.t. to 1 in new element). 4: to get count of elements of same size as new element but greater (i.e. 1 at at least one position or 0 w.r.t. to 0 in new element). 5: count of elements equal to new elements (since we added this two times through dfs-3 and dfs-4). ans=val1+val2+val3+val4-val5. And zero is special case so considered it separately.

@sdssudhu Can you explain your trie solution ? I tried to come up with it but couldn’t do so.

Added. ‌‌‌

thank you for it