Monday, February 17, 2020

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(k3) 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 c1c2, ..., ck. What is the minimum cost to reach position (m<=109)?


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!

Sunday, February 9, 2020

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 1012 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.

Tuesday, January 28, 2020

Best problems of 2019

Just like last couple of years (2017, 2018), I've went through the problems I mentioned in 2019 to find the ones I liked the most. I have also looked at some of the problems recommended in this post, in this post, and in various private messages. Of course, this is still an entirely subjective exercise, and it is certainly easier for me to like a problem that I have solved or tried to solve than one that I did not. Here is the shortlist (for those interested, here is a slightly bigger one), as usual in chronological order:
  • The Open Cup problem "Alien Invasion" about finding an area of a polygon by interactively asking about areas of convex hulls, by ???, with solution in this post.
  • The AtCoder problem "Triangular Lamps Hard" about finding the original state of a cellular automaton on a triangular grid, by rng_58 and yosupo, with solution in this post.
  • The Open Cup problem "Equanimous" about inserting + and - between digits of a number to get the smallest positive value and grouping all numbers in a large segment by that value, by tangjz, with solution in this post.
  • The TopCoder problem "SpanningSubgraphs" about counting spanning subgraphs with each number of edges, by lewin, with solution in this post.
  • The IOI problem "Split the Attractions" about splitting a graph into three parts of given size such that at least two are connected, by LGM and Saeed_Reza, with solutions discussed in this Codeforces post.
Which one do you think is the very best? Also, please help me fill the unknown problem authors in comments!

Monday, January 27, 2020

TCO20 stage 2 leaderboard

Since the official leaderboard for TCO20 stage 2 is not yet ready, I've put together a small script to compute it. Here's the current top 30:

RankHandleScorePoints
1Petr143206.22
2tourist133309.85
3lyrically122646.81
4bqi343122301.09
5Um_nik102383.93
6hitonanode101588.43
7yosupo91537.25
8_aid91506.97
9natsugiri91485.10
10kmjp91464.26
11maroon_kuri91232.54
12neal_wu91152.15
13IH1998041291134.90
14ShadoWsaZ81328.25
15KevinWan71516.60
16ksun4871349.06
17Egor71149.52
18redocpod71140.82
19Vasyl[alphacom]71120.55
20cerberus977781.12
21socketnaut7552.92
22Kalam13261623.00
23KKT8961396.76
24ecnerwal61245.65
25darnley6846.29
26kuniavski6821.25
27square10016788.87
28keymoon6777.42
29nwin6763.49
30Jatana6640.78

Enjoy! In the future I will most likely just rerun the notebook instead of making new posts, so the updated standings will appear there.

Sunday, January 26, 2020

A cyclotomic week

TopCoder SRM 776 was the main event of this week (problems, results, top 5 on the left, analysis). After the coding phase it seemed as if bqi343 would catch up with me in the TCO20 race, but I was quite lucky twice: first, since my incorrect solution for the 1000 passed the system tests; second, since bqi343's 250 has failed. As a bonus, now I have learned about cyclotomic polynomials (I guess it's more like re-learned — surely my mathematician degree should have got me covered here).

The medium problem was very nice as well. 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.

In my previous summary, I have mentioned a sub-problem of another TopCoder problem: for which pairs of positive integers a <= b can we split all integers from the set {a, a+1, a+2, ..., b-1, b} into two parts with equal sum?

First of all, the sum of all numbers (a+b)*(b-a+1)/2 must be even. Since the two parts in the product (a+b)*(b-a+1) have different parity, one of the parts must be divisible by 4 for the sum to be even. In case the size of the set (b-a+1) is divisible by 4, we can always make such a split: for each four consecutive numbers, we can split them independently as x+(x+3)=(x+1)+(x+2).

Now, what happens when (a+b) is divisible by 4? The size of the set is odd in this case, so we must split into two unequal parts, the smaller part will have at most (b-a)/2 elements, and the bigger part at least (b-a)/2+1 elements. The sum of (b-a)/2 biggest elements in the set is equal to (b-a)/2*(b+b-(b-a)/2+1)/2=(b-a)*(3b+a+2)/8. The sum of (b-a)/2+1 smallest elements in the set is equal to ((b-a)/2+1)*(a+a+(b-a)/2)/2=(b-a+2)*(3a+b)/8. If the former is smaller than the latter, clearly there's no good split as the smaller part will always have the smaller sum.

It turns out that this condition is not just necessary but also sufficient: if we can somehow get the smaller part to have bigger or equal sum, we can make it have equal sum because we can always repeatedly decrease the sum by 1: find two numbers x and x+1 such that x is in the bigger part and x+1 is in the smaller part, and swap them. This argument is the most beautiful part of the solution in my opinion.

The condition (b-a)*(3b+a+2)/8>=(b-a+2)*(3a+b)/8 can be simplified as b>=a+2*sqrt(a), thus our final answer looks like:
  • either b-a+1 is divisible by 4, or
  • a+b is divisible by 4 and b>=a+2*sqrt(a).
Thanks for reading, and check back next week (hopefully for the best problem of 2019 vote as well)!

Tuesday, January 21, 2020

A mathematics week

There were two rounds last week. TopCoder SRM 775 took place on Thursday (problems, results, top 5 on the left, analysis). Tourist has earned a commanding victory while having the fastest time on all three problems, which also meant that nobody could get the 5 points towards the TCO20 qualification. Well done :)

The main part of the hard problem was a nice puzzle that could well appear in a mathematics olympiad: for which pairs of positive integers a <= b can we split all integers from the set {a, a+1, a+2, ..., b-1, b} into two parts with equal sum?

Codeforces Round 614 followed on Sunday (problems, results, top 5 on the left, analysis). There was just one accepted solution for each of the two hardest problems, coming from Um_nik and tourist who have therefore occupied the first two places with a huge margin. Um_nik's problem was worth more points, and he had therefore won the round. Congratulations!

Thanks for reading, and check back next week!