MINMAXOR - Editorial

PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Permutations

PROBLEM:

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.

EXPLANATION:

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.

Explanation

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.

Proof

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

0,B+0,B+1,1,2,B+2,B+3,3,\dots

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.

Proof

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.

Proof

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.

TIME COMPLEXITY:

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)

SOLUTIONS:

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