PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
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}:
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:
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:
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