A doubles week

The March 28 - April 3 week was ignited by Monday's VK Cup 2016 Round 1 on Codeforces (problems, results, top 5 on the left, parallel round results, analysis). Tourist and subscriber left little doubt as to who's the favorite of the entire VK Cup, solving five problems in 1 hour and 6 minutes, while it took other teams at least 1 hour and 41 minutes to do the same!

Just a few hours later, in the early hours of Tuesday morning TopCoder SRM 686 allowed algorithmists from other time zones to enjoy some problem solving (problems, results, top 5 on the left, solutions discussion). jcvb has denied matthew99a his second consecutive win — congratulations to both on great performance!

On Sunday, the penultimate Open Cup 2015-16 round, the Grand Prix of Moscow, challenged teams with some really difficult, if a bit tedious, problems (results, top 5 on the left, analysis). Team SPb SU Base demolished the competition, solving half of their problems in the last hour!

My personal favorite in this round is problem A. Its submission stats: 296 submitted, 0 accepted. And the problem was just about implementing binary search on n choices in log₂(n) time :)

More precisely, one needed to interactively guess a hidden number between 1 and n (which was up to 10⁹) spending at most log₂(n+1)+0.1 steps on average. One guess was asking "is the hidden number less than x?" for any value of x. The guessing was repeated 10000 times with possibly different (and possibly the same) hidden numbers to compute the average.

Where's the catch? In the lack of rounding. Normal binary search requires ceil(log₂(n)) steps in the worst case, and we can't afford that much here. If the hidden number was also random, then we'd get the required number of steps on average — but it's not.

For example, suppose n=6. Normal binary search requires 2 or 3 steps: it starts by splitting the numbers into [1,2,3] and [4,5,6]. Suppose the hidden number is in [1,2,3]. Then it splits the numbers into, say, [1] and [2,3], and in case the hidden number is 1, we've found it in 2 steps, while for 2 and 3 we require 3 steps. We could've split the triple into [1,2] and [3] instead, solving 3 in 2 steps and 1 and 2 in 3 steps, so one might expect that randomizing this choice will make our solution work under our limit of log₂7+0.1=2.907... on average. But on closer examination, we always require 3 steps for the number 2 (and for 5)! So if we're always asked to find 2 or 5, then we will not fit under the required average number of steps.

In other words, for n=6 we have to split the numbers into 2+4 instead of 3+3 sometimes! And to add insult to injury, we also have to take our previous decisions into account as the binary search narrows down. For example, suppose n=5. Most probably we'd start with 2+3 or 3+2 split for the first request, for symmetry reasons with probability 50% for each decision. Note that all numbers are not equal now: if number 3 is hidden, then we'll always get the bigger segment as the answer for our query! So in order to get a good number steps on average when 3 is hidden, we have to prefer splitting the remaining numbers as [1,2] vs [3], as opposed to [1] vs [2,3]!

This is where our team got stuck at the actual contest :) Can you see how to progress further?

Thanks for reading, and check back soon for last week's summary and this problem's solution!