A frontier week

TopCoder SRM 778 took place last week (problems, results, top 5 on the left, my screencast, analysis). I and many others have come up with a O(k³) solution for the medium problem that was unexpected for the problemsetters, which however required some squeezing into the time limit with k=1000. I have used two main insights to do so:

• A "backward" DP which computes a number based on previous numbers is faster than a "forward" DP that updates further numbers based on the already computed number, presumably because it does less memory writes and those writes are sequential.
• C++ is faster than Java :)

The intended solution for the problem was actually much nicer than that. Here is the problem statement, after some unwrapping: 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⁹)?

Open Cup 2019-20 Grand Prix of Gomel has then resumed the Open Cup season after the New Year break (results, top 5 on the left, analysis). Team Polish Mafia was just 100 penalty minutes ahead of Yuhao Du, who was seemingly competing alone. Congratulations to the Mafia but also very impressive from Yuhao!

Thanks for reading, and check back next week!