A repeated doubling week

The Feb 17 - Feb 23 week had quite a bit of contest activity. Codeforces Round 621 took place right on Monday (problems, results, top 5 on the left, analysis). MiFaFaOvO, 300iq, ohweonfire and yosupo got their last accepted problem around the same time, but MiFaFaOvO had resubmitted D and was done much faster otherwise, hence the higher score. Well done!

TopCoder SRM 779 followed on Friday (problems, results, top 5 on the left, analysis). I've tried to dig a hole for myself this time, first resubmitting the 450 while my original solution was correct as well, then earning -50 on challenges that put me out of the top 10, only to finally get a +50 and cling to the 10th place (which gives 4 points towards the TCO qualification) by less than one point :)

maroon_kuri on the other hand did everything better, including finding a challenge to jump into the first place. Congratulations!

Open Cup 2019-20 Grand Prix of Zhejiang, also known as Yuhao Du Contest 7, took place on Sunday (results, top 5 on the left). Only this comment made me notice the unusual numbering system for Yuhao Du contests, and it's totally justified :) Team Polish Mafia's 5 solved problems is a truly impressive achievement, well done!

Problem G (which we didn't get accepted during the contest because of a small bug) had no input and challenged one to find three points in three-dimensional space with integer coordinates up to 10⁶ that would present a hard testcase for floating-point geometry code. More specifically, let's project these three points to the unit sphere (x/sqrt(x²+y²+z²), y/sqrt(x²+y²+z²), z/sqrt(x²+y²+z²)). The plane passing through those projections must pass very close to the origin, but not exactly through it: the distance from the origin to this plane must not exceed 1.5*10^-19. Moreover, probably for the sake of the numeric stability of the checker, the three points have to be far apart on the unit sphere: at least 1.7 from each other (note that the diameter of the unit sphere is 2).

VK Cup 2019-20 Elimination Round wrapped up the week (problems, results, top 5 on the left, parallel round results, analysis). Nobody was able to solve all problems either in the official round or in the parallel one, so choosing the right set of problems to tackle was very important this time. tourist did the best job on that front, and won the round convincingly — congratulations!

Problem D looked quite puzzling, but had a very short solution. You are given a complete directed graph on n vertices (n<=80), with each arc having its own non-negative cost. Your goal is to find a cyclic route of length exactly k (k<=10) from vertex 1 to itself with the lowest possible cost such that this route does not have sub-cycles of odd length (therefore k is always even). Can you see the short solution?

In my previous summary, I have mentioned a TopCoder problem: you start in position 0 on a line, and can make jumps of integer size between 1 and k (k<=1000) to the right, increasing your position. You are given the costs of such jumps as c₁, c₂, ..., c_k. What is the minimum cost to reach position m (m<=10⁹)?

The key idea is that if we know the minimum cost to reach positions x-k, x-k+1, ..., x+k then we can determine the minimum cost to reach positions 2x-k, 2x-k+1, ..., 2x+k! The reason for this is: our maximum jump is k, therefore there is always an intermediate stopping point within k/2 of any point in any jump sequence. Consider the jumping sequence that reaches 2x+t, and find its intermediate stopping point that is the closest to its middle point, x+t/2: let this stopping point be x+t/2+u. Since both t/2 and u do not exceed k/2 by absolute value, this point is between x-k and x+k! And the distance from this point to 2x+t is also between x-k and x+k for symmetrical reasons. Therefore if we try to combine all pairs of optimal answers for x-k, x-k+1, ..., x+k, we will obtain all optimal answers for 2x-k, 2x-k+1, ..., 2x+k.

This step works in O(k²), and we can use the repeated doubling approach to solve the entire problem in O(k²*log(m)). It is also remarkable that this problem can in fact be solved in O(k²) if we're guaranteed that m>=k² (and therefore we can achieve O(k²*log(k)) in the general case) by running a shortest paths algorithm on remainders modulo the best step (the one with the smallest cost/length ratio).

Thanks for reading, and check back for more!