An intriguing week

Codeforces Round 604 took place during the Dec 2 - Dec 8 week (problems, results, top 5 on the left, analysis). MiFaFaOvO has won the round, taking some advantage from the fact that problem E has appeared before, but still solving F in a bit more than half an hour while his competitors could not do that in an hour. Well done!

Open Cup 2019-20 Grand Prix of Beijing wrapped up the week on Sunday (results, top 5 on the left). Team Past Glory has continued to break away in the overall standings, winning the round and solving all problems to boot (they would still have won even without solving D at the end of the contest). Congratulations on the win!

In my previous summary, I have mentioned my NEF problem: there are 2n elements (n>=3). We can compare any two elements, and there are no equal ones, so one will compare bigger than the other. Our goal is to make such set of comparisons that uniquely determines the n biggest elements out of 2n, but not the ordering of those n elements. In other words, there must be at least two possible orderings of those n elements that are consistent with the outcomes of comparisons.

For large values of n, since the n biggest elements can be determined in O(n) and sorting them requires O(n*logn), just applying any O(n) algorithm will do as we will not do enough comparisons to determine the order, and some randomized approaches also work. The real problem lies in tackling small values of n, roughly between 3 and 7.

One could imagine that for such small inputs we could do some kind of exhaustive search, but it turns out that already for n=6 the state space is enormous as we have 12! possible inputs. Therefore, we need to come up with an actual algorithm :)

Initially I did implement the exhaustive search to find a solution for n=3, and then came up with a way to obtain a solution for n+1 from a solution for n. However, together with Pavel Kunyavskiy we could come up with a simpler approach.

Let us take arbitrary n+1 elements and split them arbitrarily into two groups of size at least 2, for example of size 2 and n-1. Now let's find the smallest element in each group in any possible way (using only comparisons within the group), and then compare those two elements between themselves. The one which compares smaller is the smallest among the n+1 chosen elements, and therefore is not among the n biggest elements, so we can discard it from consideration.

Now let's add one more element to one of the two groups in such a way that both have size at least 2, and repeat the step above, discarding one more element from consideration. We repeat this until there are no more elements to add (discarding n elements in total).

In the end we're left with the n biggest elements split into two groups, and we have never compared any element from the first group to any element of the second group, therefore there are at least two (more precisely, at least three) possible orderings of those n elements.

Thanks for reading, and check back for more!