# Yet Another Minimax Problem

# Yet Another Minimax Problem

+ 8 comments Question explained in detailed:

Let's take the first test case. Our array is [1,2,3,4].

First find all its permutations and their score.

Score of a permutation in the maximum of all the values we get by xoring neighbouring elements in the permutation.

In this case:

[1, 2, 3, 4] --> score = max(1^2, 2^3, 3^4) = max(3, 1, 7) = 7 [1, 2, 4, 3] --> score = max(1^2, 2^4, 4^3) = max(3, 6, 7) = 7 [1, 3, 2, 4] --> score = max(1^3, 3^2, 2^4) = max(2, 1, 6) = 6 [1, 3, 4, 2] --> score = max(1^3, 3^4, 4^2) = max(2, 7, 6) = 7 [1, 4, 2, 3] --> score = max(1^4, 4^2, 2^3) = max(5, 6, 1) = 6 [1, 4, 3, 2] --> score = max(1^4, 4^3, 3^2) = max(5, 7, 1) = 7 [2, 1, 3, 4] --> score = max(2^1, 1^3, 3^4) = max(3, 2, 7) = 7 [2, 1, 4, 3] --> score = max(2^1, 1^4, 4^3) = max(3, 5, 7) = 7 [2, 3, 1, 4] --> score = max(2^3, 3^1, 1^4) = max(1, 2, 5) = 5 [2, 3, 4, 1] --> score = max(2^3, 3^4, 4^1) = max(1, 7, 5) = 7 [2, 4, 1, 3] --> score = max(2^4, 4^1, 1^3) = max(6, 5, 2) = 6 [2, 4, 3, 1] --> score = max(2^4, 4^3, 3^1) = max(6, 7, 2) = 7 [3, 1, 2, 4] --> score = max(3^1, 1^2, 2^4) = max(2, 3, 6) = 6 [3, 1, 4, 2] --> score = max(3^1, 1^4, 4^2) = max(2, 5, 6) = 6 [3, 2, 1, 4] --> score = max(3^2, 2^1, 1^4) = max(1, 3, 5) = 5 [3, 2, 4, 1] --> score = max(3^2, 2^4, 4^1) = max(1, 6, 5) = 6 [3, 4, 1, 2] --> score = max(3^4, 4^1, 1^2) = max(7, 5, 3) = 7 [3, 4, 2, 1] --> score = max(3^4, 4^2, 2^1) = max(7, 6, 3) = 7 [4, 1, 2, 3] --> score = max(4^1, 1^2, 2^3) = max(5, 3, 1) = 5 [4, 1, 3, 2] --> score = max(4^1, 1^3, 3^2) = max(5, 2, 1) = 5 [4, 2, 1, 3] --> score = max(4^2, 2^1, 1^3) = max(6, 3, 2) = 6 [4, 2, 3, 1] --> score = max(4^2, 2^3, 3^1) = max(6, 1, 2) = 6 [4, 3, 1, 2] --> score = max(4^3, 3^1, 1^2) = max(7, 2, 3) = 7 [4, 3, 2, 1] --> score = max(4^3, 3^2, 2^1) = max(7, 1, 3) = 7

Our answer is the minimum of these scores. In this case, it is 5.

[deleted] + 7 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,

11100010101 11110101010 11010101011 11100010000 11111001010 11000111110 11011111010.

The value of any permutation is left unchanged by trimming leading

`1`

s that occur on every number:`XOR(1,1)=0`

. Post-transformation sequence for the example above:100010101 110101010 010101011 100010000 111001010 000111110 011111010.

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:0XXXXXXXX 0XXXXXXXX 0XXXXXXXX <-- A 1XXXXXXXX <-- B 1XXXXXXXX 1XXXXXXXX 1XXXXXXXX.

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).

+ 2 comments Hi. There seems to be a lot of confusion in so many comments, despite the excellent insights from suraj_patel_95. I'll try to explain in a slightly different way.

First, if all the values submitted are the same, the answer is 0 (value xor's with itself). Assuming there are different values submitted, the answer is > 0, because anything xor'ed with a different value is non-zero.

Some values are greater than others, of course. Ignore the first part of Suraj's comment for the moment, and assume that some values have a most significant bit (msb, or leftmost bit) in a higher position than others, e.g, decimal: 3, 2, 1; binary: 11, 10, 01. The msb of 2, 3 is at position 2, the msb of 1 is at position 1.

Among the permutations, there must be some (or one) such that all the values with msb in the highest position follow all the values with msb in a lower position. From an implementation standpoint, partition these into two sets (arrays, trees, whatever). Unlike for permutations, order within each partition is not important. E.g. for input 3, 2, 1, it could be {1},{2,3} or {1},{3,2}. Permutations like this will have their highest xor result (score) when the last value from the "small" partition is xor'ed with the first from the "big" partition. This is so because only that result has its msb in the same position as the "big" values; that bit will become zero when big values xor with each other.

The answer is obtained by xor'ing all the smaller values with all the larger and selecting the smallest. Why? Because among permuations such as described above, there must be some in which those two values that give the smallest result are adjacent. This problem now becomes O((n/2)

^{2}), worst case, and O(n) best case (if only one value is in one of the partitions). (Better if you're lucky enough to find a result of 1 early, just return that!)Now the little catch. Suppose all values have msb in the same position, e.g. decimal: 9, 13, 12; binary: 1001, 1101, 1100. Then it's necessary to strip the msb from all values, and if the next msb is in the same position for all values, strip that as well, and so on.

Hopefully Suraj's comment will now make more sense to those still confused. For those new to bitwise operations, below is the code in Java for determining the position of the msb for a 32 bit integer.

static int leftBit(int val) { int msb=1<<31; while((msb&val) != msb) msb>>>=1; return msb; }

Good luck

Mark

+ 1 comment I've come back to this question 5 times now, and I still don't understand what it is asking for. Even reading every comment word for word, and following the (very poor) examples, this one needs someone to re-write the question in English. It keeps mentioning find the minimum, then everyone just gives a maximum for the right answer, and fanfares reign.

I'm really not interested in a correct answer, so please don't post one, I just need a correct question.

+ 0 comments What is the best-time complexity can this problem achieve?

Sort 31 Discussions, By:

Please Login in order to post a comment