MINMAXOR - Editorial


Contest - Division 3

Contest - Division 2

Contest - Division 1






You are given a set \{0,1,2,\dots,2^N-1\}. Determine the number of permutations of the set such that, the maximum bitwise XOR of any even length sub array is minimised. Also output one such permutation.


Define the cost of a permutation as the maximum bitwise XOR over all even length sub array’s of the permutation.

Let X be the minimum possible cost over all permutations. Then, we are trying to find - (1) the number of permutations with cost X and, (2) output one such permutation.

Hint: Brute force helps. Try N=3 and try finding X.


Observe the pattern (derived using brute force code):

  • N=1 \to X=1
  • N=2 \to X=2
  • N=3 \to X=4

It looks like X = 2^{N-1}, which is a good start.
We try proving this conjecture below.

Claim: X=2^{N-1} describes the relation between X and N.


Let’s start by showing X \nless 2^{N-1}.
It is easy to show that, in every permutation, there exists some a\ge2^{N-1} and b<2^{N-1} adjacent to each other. And their bitwise XOR is always \ge 2^{N-1}. This implies X \nless 2^{N-1}.

A bit of experimentation gives a sequence with X=2^{N-1}:


where B=2^{N-1}. It’s not hard to see that the bitwise XOR of any even length sub array is \le 2^{N-1}. Thus, the claim stands proved.

Now, all we are left to find is the number of permutations whose cost equals X=2^{N-1} (an optimal permutation is presented in the above spoiler).

Claim: The cost of a permutation P is not affected by cyclic shifts of the permutation array.
(The proof is left to the reader as an exercise. Use the fact that (apart from the trivial N=1) the XOR of all elements of the permutation is 0; thus the XOR of any sub array is equal to the XOR of the remaining elements in the array)

Represent a number as S if it is < 2^{N-1}, and B otherwise.
Claim: If a permutation has cost X, every S in it has an adjacent B.


We prove by contradiction.
Assume there exists a permutation with cost X, such that some cyclic shift of the it has a S with no adjacent B. The permutation would look something like this:

\dots SSSB\dots

Since the cost of the permutation is X, the bitwise xor of the 3^{rd} and 4^{th} visible elements is bound to be 2^{N-1} (by the definition of S and B). And since the elements are distinct, the XOR of the 1^{st} and 2^{nd} elements is strictly between 0 and 2^{N-1}.
This implies that the XOR of the 4 elements is > 2^{N-1}, a contradiction (since the cost of the permutation is 2^{N-1}).

And we are done.

Claim: Every B should have exactly one S adjacent to it.


From the above claim, we know that each S should have at least one B adjacent to it. Since the number of S's is equal to the number of B's, each B should also have at least one S adjacent to it.

If a B has more than one S adjacent to it (as in \dots S_1BS_2\dots), then either S_1\oplus B or B\oplus S_2 is > 2^{N-1}, breaking the optimality condition.
Thus proved.

From the two claims above, it isn’t hard to deduce that the pattern should be of the form \dots SBBSSBBS \dots where adjacent S and B are i and i+2^{N-1}, respectively (0\le i<2^{N-1}).

A bit of case work gives us a total of 4 definite patterns:

  • BBSSBBSS\dots
  • BSSBBSSB\dots
  • SSBBSSBB\dots
  • SBBSSBBS\dots

So, how many ways are there? Pairing each i and i+2^{N-1} gives us 2^{N-1} pairs, which can be permuted amongst themselves and arranged in one of the four patterns, giving us a grand total of 4*(2^{N-1})! ways.

The case where N=1 can be handled separately.


Calculating the factorial in the answer takes O(2^{N-1}) time. Generating one required sequence takes O(2^N). The total complexity per test case is therefore:

O(2^{N-1}+2^N) \approx O(2^N)


Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters