Hints: GCD is Greater

• How to flip all bits in a number.
• How to extract the i-th bit.
• How to compute gcd.

The new gcd would either remain same, or it would increase. In other words, gcd is a monotonically increasing function if you keep on removing elements from the box one by one.

This might out sound out of the blue to some of you, but this argument has appeared in CF editorials a good number of times. For example, given an array, you can claim that

The gcd of all subarrays starting at i would only keep on falling, each time you append an element. Each time it falls, it drops at least by a factor of 2. Therefore, there can only be a total of O(log(n)) distinct gcd values of all such subarrays.

The bitwise AND would either remain the same, or it would decrease. Because each time you introduce an element, it has the potential to turn off the i-th set bit of current bitwise AND given the i-th bit of the incoming number is off. Of course, it cannot turn on any unset bit. This leads us to a very important observation:

Bitwise AND is extremely restrictive.

Why are we emphasizing on this fact? Beacuse even if one unset bit is present in the i-th position, the resulting AND can never have the i-th bit set.

Remember this fact, this will be a crucial observation in Section 2.

The given equation is

gcd(red) > and(blue) + x

Suppose I randomly select a subset of red and blue elements, and I give you the option of transferering some elements between the boxes. Is it in your best interest to do the transfers to increase your chances of satisfying the above equation? Why?

gcd(red) > and(blue) + x

Note that x is fixed. So we can only tune the red box and blue box. Of course, to maximize our chances, we should aim to achieve the highest gcd of red box (LHS) while simultaneously making the bitwise AND of the blue box as small as possible (RHS).

Given an opportunity, we should ALWAYS transfer one element from the red box to the blue box. Because removing an element from the red box will possibly increase the gcd and inserting that element into the blue box will possibly increase the bitwise AND, which is exactly what we want.

This also explains why in Hints 1 and 2, we were taking things out from the red box, but inserting them into the blue box.

So, you should always do the transfers if it is possible. When would it not be possible? When the size of the red box becomes the smallest, i.e. 2.

Therefore, we have an important breathrough in the problem.

We just need to label 2 elements red and n - 2 elements blue to see if we can satisfy the given equation.

This breakthrough is enough to solve the O(n^3) and O(n^2) variant. You should close the hints and code up these variants. You should get the following verdicts.

• O(n^3) : TLE on Test 9
• O(n^2) : TLE on Test 12

To solve the O(n^3) variant, simply iterate over all pairs (i, j) which are red, and manually compute the bitwise AND of the remaining elements.

Code

To solve the O(n^2) variant, we need a way to quickly compute the bitwise AND of n - 2 elements. To do that, we can maintain the count of zeroes at each bit position, then, when we color a[i] and a[j] as red, we remove their contribution from each bit position. Finally, we can recover the bitwise AND of the n - 2 elements if we know the total number of set bits at each bit position.

Code

Now, how do we optimize it to O(n log(n))?

P.S: Please ignore the missing log(n) factor for computing gcd in the entire article.

If you want to challenge yourself, here’s a vague hint for the final solution.

Since Bitwise AND is so restrictive, for every bit position, you can either color certain elements red and see if you got an answer, or you can “lock” that position making the bitwise AND fixed.

You should be able to answer these questions without blinking twice.

• Find the maximum pairwise gcd in an array.
• Find the number of pairs with gcd g.
• Find the sum of gcd of all pairs of an array.

Let’s also store all the indices which have the j-th bit unset. And let’s iterate over all the bits one by one.

Suppose you’re dealing with the j-th bit. You see that

• No element has a zero at that position.
• Only 1 elements has a zero at that position.
• Only 2 elements have a zero at that position.
• More than 2 elements have a zero at that position.

What can you say about the j-th bit of the final set of blue elements in each such scenario?

If all the j-th bit are set. Then, we can for sure say that the final answer would also contain the j-th bit set. Similarly, if there are more than 2 unset bits, then the final answer will the j-th bit unset. In these cases, the j-th bit of the answer is “locked”.

What if there are 1 or 2 unset bit? For that, we need to determine if it’s feasible to put them in red set or blue set. But a simple bruteforce works. Pick one such element, and naively match it with all other elements to see if you get the desired equation satisfied. If you did not find an answer, then definitely this element has to be in the blue set, and due to this, the j-th bit of the blue set is again locked. (i.e, it will be unset in the answer).

So, in either case, for each bit, you either find the answer, or the bits of the bitwise AND of the blue set are locked. This means that the bitwise AND is fixed and known beforehand. With this info, can you figure out the rest of the solution?

You just need to find

gcd > x + constant_and

The maximum pairwise gcd should be greater than a constant.

So, essentially, you just need to find if there is a pair with gcd > k. This is a standard problem (as mentioned in the prerequisite). You simply iterate over all g from max downto 1. Then, you check if there are at least 2 elements that are multiple of this gcd. If yes, you have your answer.

This algorithm doesn’t produce an answer with gcd g, rather it produces an answer with gcd with gcd as a multiple of g. But in our case, both these are equivalent, since we are iterating from high to low, we would reach the higher gcd first and break out of the loop.

This solution is mostly correct, except for one small bug, which you might’ve alredy noticed (You’d get WA3 with this implementation). Can you guess what we missed?

We can’t just compute the maximum pairwise gcd by locking the bitwise AND. Note that the bitwise AND is automatically locked where unset bit count is zero or >= 2. But for the case of 1 or 2 unset bit, we actually need to sacrifice one element to the blue set to lock down the j-th bit as zero. This means that it reduces our chances of finding the maximum pairwise gcd because the sacrificed a[i] is not contributing anymore.

But that’s all right, we already tried coloring a[i] as red to see if we can find an answer. We didn’t. So it has to go to the blue set.