DIFFICULTY:
3494
First, let’s determine when for an array A_1, A_2, \ldots, A_N exists an integer C such that A_1 \oplus C < A_2 \oplus C < \ldots < A_N \oplus C.
Choose any 1 \le i \le N-1. Let j be the largest bit where A_i differs from A_{i+1} (if A_i = A_{i+1}, there is clearly no such C). Then, if 2^j is set in A_i and not in A_{i+1}, it should be set in C, otherwise it shouldn’t be set in C.
Clearly, such C exists only if there is no bit for which we get contradictory conditions. That is, there can’t exist 1 \le i_1, i_2 \le N-1 and bit j, such that for 2^j is the highest differing bit for both (A_{i_1}, A_{i_1 + 1}), (A_{i+2}, A_{i_2 + 1}), and it’s set in A_{i_1}, A_{i_2 + 1} and not set in A_{i_1+1}, A_{i_2}.
Now, we need to check if there exists B such that there are no such i_1, i_2, j for array A_1 + B, A_2 + B, \ldots, A_N + B.
Lemma: If such B exists, there exists such B < 2^{31}.
Proof: Consider the smallest such B. Suppose that B \ge 2^{31}. Consider numbers A_1 + B, A_2 + B, \ldots, A_N + B.
-
Suppose that all of them have the same highest set bit 2^j, and j \ge 31. Then, if B\ge 2^j, we can replace B by B - 2^j, and all the conditions will still clearly be satisfied. Otherwise, B < 2^j. Note that then A_i + B < 2^{30} + 2^j, so the bit 2^{j-1} in each A_i + B is not set. Also, B \ge 2^{j-1}, as otherwise we would have A_i + B < 2^{30} + 2^{j-1} \le 2^j for each i. Then, we can replace B by B - 2^{j-1}, and it will work (all numbers will have the same highest bit 2^{j-1} instead of 2^j, and nothing else will change.
-
Suppose that not all of them have the same highest bit. Suppose that the highest bit set in some of them is j. As each A_i + B \ge 2^{31}, j \ge 32. Now, there exists some A_k such that A_k + B \ge 2^j, and there exists some l such that A_l + B < 2^j. Let’s call i big if A_i + B \ge 2^j, and small otherwise.
It’s easy to see that B is in range [2^j - 2^31, 2^j - 1] then. It’s also easy to see that then for each big i, A_i + B doesn’t have bit 2^{j-1}, and for each small i, A_i + B has bit 2^{j-1}. We can also infer that all big elements form some prefix or some suffix (so that the condition for bit j holds). Then, replace B by B - 2^{j-1}. Everything will basically remain the same: for each big i, we will delete bit 2^j and add 2^{j-1}, for each small we will just delete bit 2^{j-1}, so the condition for bit j-1 will still be satisfied, and all other bits won’t even change. Proof completed.
Now, we can just check each B from 0 to 2^{31} - 1!
But how…
Let’s see how the condition on B looks for a fixed bit j. For each 1 \le i \le N-1, consider $B$s such that the highest bit where A_i + B, A_{i+1} + B differ is 2^j. It’s easy to see that these $B$s form (at most) 2 ranges modulo 2^{j+1}. Find such ranges for each i.
Now, let L be the union of such ranges for all i such that A_i < A_{i+1}, and R be the union of such ranges for all i such that A_i > A_{i+1}. The forbidden values of B are those at L \cap R.
Let’s now go from the highest bit to the lowest, and see which remainders are forbidden.
We already know that B < 2^{31}, so we will now have to consider all j from 31 to 0. Our set of initial forbidden remainders modulo 2^{32} is bad = [2^{31}, 2^{32}-1].
Now, for each j from 31 to 0, find the corresponding sets of ranges L, R and combine bad with L\cup R. Which remainders x modulo 2^{j} are prohibited then? Those, for which both x and x + 2^j are present in bad \cup (L \cap R). Find all such bad remainders (we keep everything as a set of ranges).
In the end, if 0 is allowed, such B exists, else it doesn’t.
Total complexity is O(N \log N \log MAX A_i)