We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Certainly an interesting challenge, and requires some insight into a general structure of a minimum possible permutation. My solution is similar to the editorial. The following is a hint:
Consider the bit structure of an arbitrary sequence of numbers aligned by their binary place. For example,
The value of any permutation is left unchanged by trimming leading 1s that occur on every number: XOR(1,1)=0. Post-transformation sequence for the example above:
Now consider a minimum permutation of this example sequence. Its value is given by the maximum XOR of two adjacent numbers in the sequence. ALL possible permutations necessarily has at least one number with a leading 0 adjacent to a number with a leading 1.
Let's suppose that we have the minimum permutation. It should be possible to convince yourself that we can generally rearrange the permutation to give a permutation of equal value which has a sequence of numbers leading with 0 following by a sequence of numbers leading with 1. For above:
The arrows point to the two values which in the minimum permutation have the maximum XOR value. This final transformed sequence obviously has its value determined by XOR(A,B) since that is the maximum possible XOR'ing of adjacent values (it is the only XOR'ing that has a 1 in the leading digit and hence is the maximum). The problem is now to find XOR(A,B).
Yet Another Minimax Problem
You are viewing a single comment's thread. Return to all comments →
Certainly an interesting challenge, and requires some insight into a general structure of a minimum possible permutation. My solution is similar to the editorial. The following is a hint:
Consider the bit structure of an arbitrary sequence of numbers aligned by their binary place. For example,
The value of any permutation is left unchanged by trimming leading
1s that occur on every number:XOR(1,1)=0. Post-transformation sequence for the example above:Now consider a minimum permutation of this example sequence. Its value is given by the maximum XOR of two adjacent numbers in the sequence. ALL possible permutations necessarily has at least one number with a leading 0 adjacent to a number with a leading 1.
Let's suppose that we have the minimum permutation. It should be possible to convince yourself that we can generally rearrange the permutation to give a permutation of equal value which has a sequence of numbers leading with 0 following by a sequence of numbers leading with 1. For above:
The arrows point to the two values which in the minimum permutation have the maximum XOR value. This final transformed sequence obviously has its value determined by XOR(A,B) since that is the maximum possible XOR'ing of adjacent values (it is the only XOR'ing that has a 1 in the leading digit and hence is the maximum). The problem is now to find XOR(A,B).