# Yet Another Minimax Problem

# Yet Another Minimax Problem

[deleted] + 6 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).

Dave_NoSleepOwl + 0 comments Thanks for the explanation. For the later part of this solution, one can use a binary tree to perform the comparison. Let the size of the set containing the pruned numbers on the above with leading 0 be M (the numbers at and above the line A), with leading 1 be K, rather then O(M*K) comparison, binary tree provides a complexity O(M+K).

wanghaitang_ufl + 0 comments Well explained. The key is to find the first bit among all the inputs where they don't have the same bit value. and also separate the inputs into two parts. For instance: 000100

000101

.......

000111

The following part is to calcuate xor(a from the above part of the array, b from the down part of the array). I saw someone mentioned to use tree structure, I am sure it works as well.

mark163 + 0 comments Thanks for the explanation. That was very helpful.

ayushr2 + 1 comment Brilliant approach. Hats off. Implemented your approach in python.

def find_answer(bin_l): while True: len_set = set(map(lambda x: len(x), bin_l)) if len(len_set) > 1: break if 0 in len_set or bin_l[0][0] == '0': return 0 bin_l = list(map(lambda x: bin(int(x[1:], 2)), bin_l)) max_len = max(map(lambda x: len(x), bin_l)) big_set = set(map(lambda x: int(x, 2), filter(lambda x: len(x) == max_len, bin_l))) small_set = set(map(lambda x: int(x, 2), filter(lambda x: len(x) != max_len, bin_l))) return min([cur_big ^ cur_small for cur_big in big_set for cur_small in small_set]) input() # don't care about n l = list(map(int, input().split())) bin_list = list(map(lambda x: bin(x)[2:], l)) print(find_answer(bin_list))

dingma129 + 0 comments you should change from

if 0 in len_set or bin_l[0][0] == '0':

into

if 0 in len_set or bin_l[0][0] == '0' or

**bin_l[0][0] == '1'**:otherwise, your code does not pass the following case

4 1 1 1 1

sgrebenkin + 0 comments [deleted]sgrebenkin + 0 comments My solution is a bit different compared to one in editorial. I don't use tree. Simply sorted array. So the first part is O(N*logN). The second part - finding the min is O(N) - straightforward finding minimum with two iterators. In editorial we have O(N*logC), where C = max(Ai). But, according to my view, it is not correct, since in editorial sorting done first as well! Check this out:

sort(a, a + n);

So it shall be O(N*logN) as well!

ARulzz + 2 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.

Sagnik_Chaudhuri + 1 comment This was really needed. Thanks.

bohemianmanish + 0 comments Thank you so much.

aakashsinghdude + 0 comments thanks for explaining this

markbriggs2 + 1 comment 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

Propreet + 0 comments great explanation..Ty

mike_littlewd + 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.

Sid_S + 0 comments The score of a permutation is the max xor of two neighbors in that permutation.

You are supposed to find a permutation that minimizes the score, and then output that score.

skovalyov + 1 comment What is minimum score in permutation ?

[deleted] + 1 comment Min sum of elements after xor for each permutations. Example: If you have (1,3,2) and after xor in each permutation you get: List((2, 1), (3, 1), (2, 3), (1, 3), (3, 2), (1, 2)). Get the tuple with min sum and after max value in tuple. if you have more then one tuple with min sum you get max in any of those tuples. That is result.

priyaranjan_saps + 1 comment dude the way you have written the last line, no one can understand what exactly are you trying to say...

[deleted] + 0 comments Correct. I have erased part of comment. Really confuse the last paragraph. That solution get timeout in various tests but that is the idea this is one window on sequence of numbers.

jEeTu_pYthOn + 0 comments my python 3 code but there is terminate due to timeout can anyone help me:

from itertools import permutations a=int(input()) b=input().split(' ') l=[int(i) for i in b] l1=permutations(l) l2=[] l3=[] for i in l1: for j in range(len(i)-1): l2.append(i[j]^i[j+1]) l3.append(max(l2)) l2=[] print(min(l3))

ankitrj + 0 comments Hint : No need of tries for this question

There will be two cases only

1) number with different bit length (easy one to handle) EX: 1 2 3 4 , length of element : 1 2 2 3 2) all number of same bit length Ex: 8 9 10 11 12, length of element : 4 4 4 4 ,for this case see the pattern for minimum values of n

bit length means length of number in binary form Example : 5 --> 101, bit length = 3

hope this help :)

ph83nam + 1 comment It is confusing to under stand the sample cases in problem:

Input | Permutation | Sum XOR

1, 2, 3 -> (2, 3, 1) -> 2 + 1 = 3 (Case 0)

1, 2, 3, 4 -> (3, 2, 1, 4) -> 1 + 3 + 5 = 9 (Case 1)

1, 2, 3, 4 -> (2, 3, 1, 4) -> 2 + 1 + 5 = 8 (Why not?)

Did I misunderstand?

hetianmu + 0 comments [deleted]

dae_fromru + 0 comments If we have sequence of (1,2,3,4), then permutation of (4,3,2,1) will give us min score of 1 (3 xor 2), and max score of 7 (4 xor 3). Isn't it?

Sort 22 Discussions, By:

Please Login in order to post a comment