A deterministic week

Codeforces hosted the Avito Code Challenge 2018 during the May 21 - May 27 week (problems, results, top 5 on the left, analysis). While OO0OOO00O0OOO0O00OOO0OO and tourist were very close during most of the contest, tourist was much faster with solving the hardest problem, and thus won with a comfortable margin in the end — well done!

In my previous summary, I have mentioned an interactive Yandex problem, which required one to locate the number n in a permutation of integers between 1 and n. You are given just the number n and can send queries to learn the permutation. Each query is a number k between 1 and n, and means "increase the number in k-th position in the array by 1". After performing the requested action, the system tells you the number of distinct values in the array (which initially contains the permutation), and you can send the next query which will be applied to the new array (which is not a permutation anymore). You must tell the original location of the number n after at most 50n queries.

The official analysis mentions a nice randomized solution, but there's actually a similar deterministic one as well. Let's increment all numbers by one in some order, for example from left to right, and for each number record the delta between the number of distinct elements after and before incrementing it. Two things happen for the number x:

1) If the number x-1 does not exist or was not yet incremented, then we lose x from the set of distinct numbers, this contributes -1 to the delta.

2) If the number x+1 does not exist or was already incremented, then we add x+1 to the set of distinct numbers, this contributes +1 to the delta.

If both of those things happen, the contributions add up, and the delta is 0.

Now let's once again increment all numbers one by one, but in reverse order to the first pass, and add the delta for each position to the delta we already remember for it. The "was already incremented" conditions will flip since we iterate in reverse order now, and thus for all numbers except 1 and n we will get exactly one -1 and exactly one +1, so the total delta will be 0.

For the number n, however, the second condition always holds, so we'll get one -1 and two +1's, for the total of +1. Similarly, for the number 1 we'll get the total of -1. This easily identifies the location of the number n after just 2n queries.

Thanks for reading, and check back for more!