Wednesday, November 14, 2018

A too difficult week

The Sep 3 - Sep 9 week started with Codeforces Round 507 on Wednesday (problems, results, top 5 on the left, my screencast, analysis). Once again the hardest problem was not solved during the round, and thus it all came down to the speed on the first four problems. Um_nik was considerably faster than the competition, finishing the four problems under an hour, and thus got a well-deserved first place. Congratulations!

Problem B in this round added a nice twist to a standard setting. This is an interactive problem in which you need to find a hidden integer between 1 and 1018. You can make queries, and in one query you give a segment [l, r] and the judging program tells you whether the hidden number lies in that segment. In case it does, and your segment has length 1 (l=r), you win. So far this is a classical binary search problem.

Here comes the twist: after each query, the hidden number can change a bit — more precisely, by at most 10. These changes do not depend on your queries — in each testcase the sequence of changes is always the same.

Can you see how to adapt the binary search for this setup? You have at most 4500 queries to win.

On Sunday, the new season of the Open Cup kicked off with the Grand Prix of Zhejiang (results, top 5 on the left). This will most likely be the most brutal contest of the year :) As I understand, this was the first "big" contest set by Yuhao Du, and the scoreboard reminds me of my own first Petrozavodsk contest, or my second TopCoder SRM. Team japan02 chose the solvable problems well and earned the victory with quite some margin. Well done!

Thanks for reading, and check back for more!

1 comment:

  1. > it all came down to the speed on the first four problems

    or challenges, as the second place shows :)