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!

An almost retired week

TopCoder SRM 777 was the first round of this week (problems, results, top 5 on the left, analysis). The hard problem was way too grungy for a 75-minute round, while easy and medium both had nasty corner cases to deal with. This has led to quite low coding phase scores which were partially compensated by quite high challenge phase scores :) neal_wu and scott_wu got 250 challenge points each and took home the monetary prizes. Well done!

The winter 2020 Petrozavodsk training camp concluded on Friday (results, top 5 on the left). NNSU Almost Retired team enjoyed a really dominant performance, especially compared to other teams who would be coming to the ICPC World Finals in Moscow in June. Congratulations!

Some of those contests will return as Open Cup rounds in the coming weeks.

Finally, Codeforces Round 618 wrapped up the week on Sunday (problems, results, top 5 on the left). MiFaFaOvO, TLE and Radewoosh were the only contestants to solve the hardest interactive problem, and a mere two points separated MiFaFaOvO and TLE at the top. TLE was briefly in first place when he scored a successful challenge two minutes before the end of the round, only to be overtaken by MiFaFaOvO's own challenge with one minute remaining. Congratulations to both!

Thanks for reading, and check back next week.

A week without branching and the best problem of 2019

Codeforces Round 616 took place last week (problems, results, top 5 on the left, analysis). Three contestants could solve five problems, but tourist's solution for the hardest problem F was so fast that he got almost a thousand points more. Congratulations on the win!

In my previous summary, I have mentioned a TopCoder problem: there are n=2*a+b pieces of string, out of which a have both ends red, a have both ends green, and b have one red and one green end, so we have n red ends and n green ends in total. We will randomly pair the red and green ends in one of n! possible ways, and tie the corresponding ends together. What is the expected number of cycles we will get? a and b are up to a million.

The first idea is to notice that if we pair just one green end with just one red end, then one of the two things can happen:

• either they have belonged to two different strings, in which case we have effectively replaced two strings with one, and the colors of its ends correspond to the colors of the other ends of the original two strings, or
• they have belonged to the same string, in which case we have formed a cycle.

In either case, the problem reduces to the same problem with n-1 strings, which means that a dynamic programming solution is on the cards. However, since both a and b are up to a million, a naive dynamic programming approach would have on the order of 10¹² states, which is too much.

However, we still have the freedom of choosing which pair of green and red ends we use for reducing the problem to size n-1. If b>0, then we will choose which green end is one of the red ends of the first green-red string paired with. The key fact is that no matter which string (green-green, or green-red) we attach to the red end of a green-red string, the new string is of the same type, since we just "extend" its green end effectively! Moreover, if we tie this string to itself (the probability of which is 1/n), we also just reduce the number of green-red strings by one. Therefore we always go from the state (a,b) to the state (a,b-1) this way, and there is no branching:

f(a,b)=f(a,b-1)+1/(2*a+b)

When b=0, we have only red-red strings and green-green strings, and thus all our choices for the first move are symmetric: we will tie a red-red string and a green-green string to obtain a red-green string. Therefore there is no branching as well:

f(a,0)=f(a-1,1)

Now we can unroll this recursion to get a simple formula that can be computed in O(a+b).

I have also ran a poll for the best problem of 2019. You can see the results on the left, and the best problem with 68 out of 174 votes is the problem Split the Attractions from IOI 2019 by LGM and Saeed_Reza. Congratulations to them and to all problemsetters of 2019!

Here is what that problem is about: you are given a connected undirected graph with n vertices and m edges, and you are also given three positive integers a,b,c such that a+b+c=n. Your goal is to split all vertices of the graph into three parts, the first of size a, the second of size b, and the third of size c, in such a way that at least two of those parts are connected using only the graph edges within the part. n<=100000, m<=200000.

Thanks for reading, and check back for more.