# Yet Another Minimax Problem

# Yet Another Minimax Problem

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

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!

jacarolan22 + 0 comments This solution is great, but you should strip off leading bits that are the same, not just leading

`1`

's, otherwise the "leading`1`

" set of values could be empty.

ARulzz + 4 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

awesomealka2004 + 0 comments thank you, so much!

amitcode563 + 0 comments In the test case explanation 3,2,1,4 is the one with minimum score. But as per your explanation 2,3,1,4 is having minimum score. PLEASE EXPLAIN!

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.

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?

poornima555 + 0 comments what is the alogorithm to find The permutation with the minimum score?

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

argha48 + 1 comment is there any better algorithm than N! to find the permutation with minimum XOR value?

radekr_ + 1 comment Of course there is, otherwise that wouldn't be a medium level problem :)

argha48 + 1 comment Will you please point me towards it?

radekr_ + 1 comment Well, the problem is that if the best you can come up with is O(n!) algorithm then there is a big gap between what you know and what you need to know :) Start with 2 random numbers, let's say 5 and 9, write them in binary form, try to xor them and look at the result. Try to make some conclusions what does exactly xor do. Then go to some small examples with let's say 4,5 numbers in an array and solve it with your O(n!) algorithm. Try to write the numbers in the binary form and try to guess why the answer looks like this. I have one hint in mind, but it may be too big, so I don't know if I should write it already. If you want to receive it just send me private message or ask to write it here.

eladmar + 1 comment can you write the algorithm here? thanks!

radekr_ + 0 comments What would be the point of writing algorithm here? If you want it, you can always unlock the editorial, right? The reason why it's hidden is to motivate you to find the solution by yourself, maybe with some tips like these in mine and other comments.

damel_lp + 0 comments has anyone got anymore test cases I could use? as mine passes for mine and I don't want to submit yet

ludopulles + 0 comments Great problem and beautiful solution. It was lucky for me that the problem has been simplified to

`n <= 3000`

, because it looks like the original problem had`n <= 200000`

, and in that case a`O(n^2)`

solution like I did, would not be accepted.

Sort 23 Discussions, By:

Please Login in order to post a comment