This week in competitive programming

The main event of this week, of course, was the ACM ICPC 2014 World Finals in Yekaterinburg (problems, results, top 5 on the left). I've passed on the joy on just being a spectator, and tried to solve the problems in real-time instead - but during the moments I was able to look at the scoreboard, it was surprisingly emotional to see my alma mater, Moscow State University, at the top of the standings. It's really sad that we're in second place for the fourth time but have never won.

The problemset was quite interesting, as usual at the World Finals, but quite heavily biased towards geometry problems. Two tedious geometry problems (J and L) went unsolved - but you can look at the excellent explanations in Bruce Merry's blog. Problems A and H were also unsolved at the contest, but they were solved at the online mirror. There's some more solution explanation at TopCoder forums, including some firsthand explanations by one of the judges - SnapDragon. And finally, here's an explanation of problem H by Gawry in Polish. Google Translate seems to give a rough idea, and it's very similar to my solution: for every "suffix" of the field (rows below a certain one), we calculate three w times w (w is up to 20) matrices, describing what happens if we enter this suffix at position i: the probability of us leaving the suffix up at position j if we enter it at position i, the probability of us finishing in the first line of the suffix at position j if we enter it at position i, and finally the probability of us finishing somewhere in the suffix but not in the first line, if we enter it at position i, and go down from it for the last time from position j.

The twelve medals were split like this: four went to Russia, three went to Mainland China, and one each to Taiwan, Japan, Poland, Croatia and Slovakia. The picture of the champions on the left is from their official VK page. Congratulations to all medalists and to all participants of the World Finals - getting there is a great achievement by itself!

I hope to see most of you again next year in Morocco :)

When most teams were back at home, TopCoder held SRM 626 (problems, results, top 5 on the left, my screencast). Somewhat standard easy and hard problems were complemented with a beautiful medium problem: you are given a directed graph with 50 vertices where each arc has two costs: expensive one and cheap one, where the cheap cost can be negative and expensive one is always non-negative. What is the cheapest path from vertex A to vertex B that uses cheap arcs at most K times?

Egor won the round by finding two challenge opportunities in a mostly dry challenge phase - congratulations! It was only fitting that the round was held on his birthday :)

Thanks for reading, and check back next week!

ACM ICPC 2014 World Finals Contest day

This post used to contain a link to auto-updating live commentary about our attempt to solve the World Finals problems in real time together with Gennady Korotkevich and Jakub Pachocki - here's the recap:

10:00 - It looks like there will be twelve problems today. Only a few moments before start.
10:06 - the problems are still not available for us, waiting for the online version of the contest to start. The real contestants are already solving them :)
10:08 - we got the problem statements!
10:13 - meret has got the idea how to solve K, that’s what we’re going to try now. The submission system is still not working, but we hope it will work by the time we have the code working.
10:33 - meret still coding K, we got the idea for C, will code it afterwards. Still no way to submit solutions. The World Finals standings shows Tsinghua submitted K, but the outcome is unknown.
11:00 - meret finished K, but the system only allowed submitting A-F at that point, so I coded C and got it accepted. Now Gennady is coding D, and we’re still waiting to be able to submit K.
11:04 - we’re finally able to submit K, and get Wrong Answer. Meret is now reading his code, while Gennady continues to code D.
11:09 - meret found a bug but still got WA after resubmitting.
11:11 - Gennady submitted D, got TLE, meret resubmitted again, got WA.
11:25 - we’ve got plenty more incorrect attempts on K, now Gennady is speeding up his D. I will code E afterwards. Not very lucky start :)
11:49 - now we have 4 problems solved: C, D, E and K. C is +, D is +2, E is +1, K is +8.
11:58 - Gennady started on B. We know how to solve G in O(N^4), but that might be too slow.
12:14 - we decided that B might time out, and decided to code the slow-ish G instead - it has more chances to fit under the time limit. Jakub is solving G now.
12:30 - meret got G coded but it doesn’t work on examples. Gennady started on B again. I’m trying to figure out the formulas in J - the problem shouldn’t be that hard after you have all the formulas :)
12:52 - meret’s G TLEs, Gennady almost ready with B. We came up with a way to speed up G from O(n^4) to O(n^3logn), will do that after we submit B.
13:07 - Gennady’s B is accepted after a WA and a bugfix. meret is now speeding up G.
13:16 - We got G accepted as well, 6 problems now! We kind of know how to solve H, will try to code it since we don’t have any better ideas.
13:59 - and H is accepted, somewhat surprising! Jakub will bruteforce A, and we’ll try to solve other problems with Gennady. 7 problems for us versus 6 for the current leader Moscow SU.
14:04 - here’s an overview of what’s left. Problem A is the constructive one, and Jakub will try to bruteforce small cases to see the pattern. Problems F, I, J, L are all geometry problems. Problems J and L are relatively straightforward algorithmically but awful to code. Problem F probably involves some kind of ternary search so it’s dangerous to solve it. Problem I should be easy to code once we have the solution, so we’re trying to solve it right now.
14:23 - we’ve discussed J with Jakub and decided that we don’t actually need any formulas and can use binary search everywhere, so it becomes tolerable. I will code it now.
14:51 - I’ve coded J for half an hour and realized I haven’t even approached the “lexicographically smallest” part, so won’t be able to finish it in time, should give up. Now Jakub is trying to code some bruteforce with pruning for A.
14:56 - That’s still too slow.
14:59 - I guess we’ll finish with 7 problems solved. Well, it was a nice contest!
15:03 - We have 7 problems and 1244 penalty minutes. Let’s see how the teams did. Thanks for reading, this story will probably not be updated anymore.

The award ceremony is going on right now, but it looks like we did slightly better than the winning teams. The top two teams are SPb SU and Moscow SU, with 1300+ penalty minutes. Of course, they were under much more pressure. Congratulations to the winners!

ACM ICPC World Finals 2014 Practice day

Tuesday started with the practice session. Back when I was competing in World Finals, the practice session had very easy problems, and it was mostly about testing the judging system behavior with respect to time, memory and stack limits. These days the practice session is called "Dress Rehearsal" and it has six quite difficult problems from the previous World Finals. Some teams chose to compete using those problems, and Zhejiang University, world champions in 2011, had the best penalty time after solving all practice problems. Of course, this will have no relevance in the real competition tomorrow.

The practice session was followed by Q&A about the judging system, and then a talk by Bill Poucher which announced several nice things: they're considering adding Python to the next year's available languages, and they're considering making the spot allocation system for the World Finals public and known in advance.

The rest of the day consisted of various fun activities for participants, like football acrobatics, dancing lessons and board games - the last two are pictured on the left. Only a few people participated in those, suggesting most contestants decided to rest in their hotels before the competition.

Tomorrow's competition will be broadcast with commentary at http://icpclive.com/ (more details in this Codeforces post), but I will still try to share my own thoughts via live commentary on this blog. Check back tomorrow!

UPDATE. According to this post, there will be an opportunity to solve the World Finals problems during the contest. In that case, I will be participating together with tourist and meret, and the commentary here will be mostly about our team's work.

ACM ICPC World Finals 2014 Opening Ceremony day

Today was the Opening Ceremony day at the ACM ICPC World Finals. In the morning, the participants listened to IBM's talks and participated in some fun activities - including a team graffiti workshop, the result is pictured on the left (photo by Pashka).

Later on, the ceremony itself took place. It was a mixture of very long talks and congratulations to people who make ICPC happen, and energetic performances by local dancers and musicians. Many awards went to people from Yekaterinburg, which makes sense given that they put tremendous effort into organizing this World Finals event - on of such awards is pictured on the right.

Some of the artistic performances were tuned to the audience, and those really stood out from the rest: the blacksmith melting metal into a smartphone, and the robots telling a story of ACM ICPC in 2187 were particularly funny in my opinion. The 'normal' performances, probably still of good quality, tended to feel disconnected from the event and thus less interesting to me. Maybe I've just missed something - was there anything else related to ACM ICPC in them?

One other topic I wanted to mention is Yekarinburg itself. I was here before, but this time the city feels much more friendly and convenient than it did a year ago. Much of it is probably due to the wonderful organizers of the World Finals who make sure everything is smooth, and the nice weather. But even taking that into account, it's still so nice :)

For example, traveling from the apartment that I rent to the ICPC zone involves taking a 20-minute tram ride, then walking along the very nice shore promenade, both without big crowds I'm so used to in Moscow, enjoying the very mixed architecture - with historic wooden buildings next to modern office towers.


Please don't get me wrong - the city is not as nice and clean as Zurich, for example. The aforementioned trams might well be older than I am and make a lot of noise, the streets still suffer from traffic jams and lots of parked cars everywhere. There is quite a bit of trash on the streets, the small city park that I randomly wandered into was just trees and mostly unpaved pathways, and construction sites form an epsilon-net in the city :) Many of the completed buildings are already deteriorating.

But still, the city feels nice and friendly both to myself in particular, and to the World Finals participants in general.

It might well be that I'm just biased for Russian cities, and tend to weigh positives way above negatives for them, though. Other World Finals participants reading this - how do you feel about Yekaterinburg? 

This week in competitive programming

The week was relatively silent with just two rounds, both on Thursday. Most competitions decided against having rounds this weekend, most probably because many of the top competitors were traveling to one of the most important competitive programming event of the year - the ACM ICPC World Finals, this time in Yekaterinburg. I will try to post some updates from the event in my blog.

TopCoder SRM 625 was the first to go (problems, results, top 5 on the left, my screencast). Like in SRM 617, the most memorable moment of the match happened during the challenge phase, where I had to come up with a challenge case against an obviously incorrect solution. This time it was not very difficult, but still cute. The medium problem had a quite complicated statement which I can't really explain in a few words - so please read it if you want to understand the problem :) The problem boiled down to finding a minimum cut where both the vertices and the edges had capacities and could be cut. The correct way to do that is to duplicate each vertex of the graph, direct all incoming arcs to the first copy, all outgoing arcs from the second copy, and connect the first copy to the second copy with an arc of capacity equal to the capacity of the vertex. This way we reduce the vertex capacity case to the edge capacity case, and then we can use the standard maximum flow algorithm to find the minimum cut. The solution in question (TopCoder login required to view) skipped the duplication, and instead just propagated the capacity of the vertex to all adjacent arcs - if an adjacent arc had a higher capacity, it was reduced to the capacity of the vertex. It's not that hard to come up with a challenge case in the graph formulation - but a bit harder in the problem's grid formulation. Can you challenge this solution?

And of course, congratulations to Bruce on the convincing victory!

Codeforces Round 253 featured problems from one of the World Finals competitors, Boris from SPb ITMO team (problems, results, top 5 on the left). Gennady "tourist" won the match and was the only contestant to solve the problem "Gena and Second Distance". The background story of this problem, quite ironically, told that Gena (a reference to tourist himself) doesn't want to solve this problem and asks you to do it instead of him. Apparently he still had to do it after all :)

Thanks for reading, and check back tomorrow for some World Finals updates!

This week in competitive programming

Last week had a lot of very different rounds.

On Thursday, the long Russia Day weekend was kicked off by TopCoder SRM 624 (problems, results, top 5 on the left, my screencast). My medium problem failed because of the following reason: it asked to find the answer modulo one billion plus nine, whereas I mechanically returned the answer modulo one billion plus seven, since the latter modulo is the standard choice in such problems. That's not a good excuse, of course, and moreover, I actually noticed that the modulo was different when reading the problem statement, but forgot about that when I started coding. Does it mean that coding the "boring" part of the solution happens almost subconsciously?..

This problem didn't stop Gennady who won with a 100+ point gap. Congratulations!

On Friday, Codeforces ran a slightly unusual round - Zepto Code Rush 2014 (problems, results, top 5 on the left). The round had prizes, but somehow that did not attract more contestants than usual: 2148 contestants submitted at least one problem, compared to 2491 in the last Div1/2 round (it happened on Sunday, so that might account for higher turnout). I've managed to do a very stupid thing again: the hardest problem from this round was a slightly easier version of a problem from Petr Mitrichev Contest 11, so I immediately knew how to solve it and could even find working code for the more difficult version. Naturally, I was the first to submit a solution, and it failed the system test - the Codeforces problem allowed items to cost 0, while my problem didn't, and the solution didn't handle those correctly.

Nikolay (KAN) didn't solve this problem but solved all the rest, added five succesful challenges, and won the round - great job!

On Saturday, 25 people won a trip to Los Angeles in Google Code Jam 2014 Round 3 (problems, results, top 5 on the left). The advancers were decided on the two most difficult problems C and D. Problem C was tricky algorithmically, but easy to code; problem D was more straightforward but had a lot of small details and required a lot of time to code. In the end nobody solved problem D in full, so people solving problem C were at the top. Congratulations to Egor on winning this round!

Early on Sunday, the 25 contestants who will go to Berlin were decided in Yandex.Algorithm 2014 Round 3 (results, top 5 on the left).

People going to the final round were decided based on the sum of three rounds, here are overall elimination round results, top 5 on the left. Evgeny (eatmore) won a very convincing first place in the overall results - congratulations! It's interesting that just 7 contestants got in top 25 in both Yandex.Algorithm and Google Code Jam: eatmore, tourist, hos.lyric, dzhulgakov, vepifanov, sdya, Jedi_Knight. Code Jam had a lot more competitors overall, but one might expect that most of the best competitors would participate in both rounds, so the randomness in such selection systems is still very big.

And finally, Internet Problem Solving Contest 2014 rounded up the week (problems, results, top 5 on the left). This is a very exciting competition that has created a format of its own. It happens just once a year and doesn't have any prizes, but it still attracts a lot of contestants, including those who don't participate in any other competitions, like Reid Barton. The reason is very simple: every year it has a very diverse set of problems, and the problems are never boring, but are always interesting and satisfying to solve. It's hard to describe what that means exactly, so I'll just provide links to different types of problems from this year's contest: a very difficult problem that could appear at a "normal" ACM-style contest, a problem requiring to analyze the hashing code in the C++ and Java standard libraries, a problem that asks you to recognize facial expressions - but only on the surface; I'm pretty sure no team who solved this problem actually analyzed the faces. Can you see the trick?

Congratulations to Reid, Tomek and John on an amazing victory!

Thanks for reading, and see you next week (well, in 4 days)!

This week in competitive programming

The week's events started with TopCoder SRM 623 (problems, results, top 5 on the left) at 5am Moscow time. Many of recent Moscow 5am SRMs have still been unexpectedly won by Russians despite the lack of sleep, but this time we got the more natural result - Mark from the United States claimed the top spot, congratulations! This was his second SRM win after almost five years delay - the previous one was SRM 447 back in August 2009.

On Friday, Yandex.Algorithm 2014 Round 2 took place (results, top 5 on the left, my screencast). The problems were more difficult than in the first round, but the optimal strategy was the same - submitting one or two problems blindly (and correctly) was enough to get a place that guarantees or almost guarantees a spot in the onsite round in Berlin.

TopCoder Open 2014 Round 2B selected another 50 lucky contestants on Saturday (problems, results, top 5 on the left). Looking at the advancers from rounds 2A and 2B by country, the top 5 countries are Russia - 25 contestants, China - 17 contestants, and Poland - 10 contestants. Last year at the same point the top 3 countries were the same, but there were 34 advancers from Russia, 12 from China and 10 from Poland - so the Chinese have made the biggest progress this year (and Russians have the biggest fall).

At the same time, the 50 advancers from Round 2A could solve the same problems in an alternative round called TopCoder Open 2014 Parallel Round 2B (results, top 5 on the left, my screencast). However, there was yet another option for people who advanced from Round 2A: they could set problems for Round 2B - and tourist did exactly that, setting the easy and the hard problems. The easy problem was a pretty greedy: you have N lamps, each lamp can be on or off, and you want to iterate through several states of the lamps in order. Each of the states describes the state of all lamps: on, off or doesn't matter. When switching from one state to another, you can switch lamps off or on, and you spend 1 minute if you don't touch any lamps, 2 minutes if you only switch some lamps on or only switch some lamps off, and 3 minutes if you do both switching on and switching off. What is the smallest time needed to iterate through given states in given sequence?

And finally, Russian Code Cup 2014 became the first competition of the current bunch to select its onsite competors in the final online round (problems, results, top 5 on the left, my screencast). 50 top finishers will come to Moscow in October for the championship round, and also receive nice gifts from the organizers: three years ago it was an iPad, two years ago it was Lego Mindstorms, and last year it was AR.Drone 2.0. Last two gifts are good examples of things software engineers will likely not buy for themselves, but are very happy to play with - so they are very good as such gifts, in my view.

The hardest problem of the round had a very simple statement: you are given two cells on an infinite grid, (x1, y1) and (x2, y2). You need to move the robot from (x1, y1) to (x2, y2) in exactly t turns, where each turn consists of moving the robot from a cell to one of its 4 adjacent cells. You're not allowed to move the robot to cells where at least one coordinate is zero or negative, and you're not allowed to visit (x2, y2) before the t-th turn. How many ways are there to achieve these goals? All five numbers in the input are up to 250000.

The problem statement also had the following clause, not very important at first sight: output the answer modulo 998244353. Many combinatorial problems ask for an answer modulo a large prime number, to allow contestants to operate within the range of the programming language's integer types. But in most cases the modulo is 1000000007 - a billion plus seven. Here, the modulo was unusual, and it was actually a very strong hint towards the solution. Not only is 998244353 a prime number, the number that is 1 less divides by a large power of two: 998244352=2²³*7*17. Why is that important? It means that there's some number X such that X²²³ = 1 (mod 998244353), and X²²² != 1 (mod 998244353). And that, in turn, allows the Fast Fourier Transform to work over remainders modulo 998244353 for polynomials of degree up to 2²³, which is conveniently greater than 250000.

Can you see how Fast Fourier Transform helps in this problem?

Thanks for reading, and see you next week!

This week in competitive programming

This week's contests started with TopCoder SRM 622 early on Thursday (problems, results, top 5 on the left). The medium problem was a nice (spoiler alert!) greedy algorithms practice. You're given a tree with edge lengths and a constant M, and need to remove some edges to separate the tree into the smallest number of connected parts in such a way that each part's diameter is at most M. A diameter of a graph is the maximum of lengths of all shortest paths between its nodes. Can you see how and why it can be solved greedily? Even the official editorial suggests to use dynamic programming here :)

This round also made SPb SU 4 an all-target (3000+ TopCoder rating) team: Dima, rating 3027, 18th in the world, Egor, rating 3019, 20th in the world, and Pasha, rating 3001, 24th in the world. Congratulations!

The weekend had a bunch of elimination rounds for "big" contests. I guess it's not that much of a coincidence - most contests have elimination rounds in spring and onsite finals in autumn. The first to go was Google Code Jam 2014 Round 2 on Saturday (problems, results, top 5 on the left). It narrowed the field from 3000 competitors still hoping to win the grand prize to 500 - just one online round left before the finals in Los Angeles!

Early on Sunday, Yandex.Algorithm 2014 Elimination Round 1 became the first test of various strategies for the blind/open format (results, top 5 on the left). Unfortunately the problems are not visible to those who's not logged in, so it doesn't make much sense to discuss them here. As for the strategies, this time getting a good result required solving six problems correctly and at least 2-3 of them blindly.

Later on Sunday, Russian Code Cup 2014 Quaification Round 4 (problems, results, top 5 on the left) was the last chance for everybody to qualify for the Elimination Round. Congratulations to Fefer.Ivan on solving all problems correctly almost half an hour before everybody else!

And finally, Codeforces Round 250 rounded up the busy Sunday (problems, results, top 5 on the left). The round had a very standard problem as problem C - to count the number of triangulations of a non-convex polygon - but it still held a surprise! The usual solution splits the problem into two parts: first, we solve the tedious geometric problem to find whether each diagonal is inside the polygon. Then, we use dynamic programming that counts the number of triangulations of each sub-polygon formed by taking consecutive edges of the polygon plus one diagonal. The dynamic programming transition is obtained by considering which will be the third vertex of the triangle containing the diagonal as its side, and thus separating the problem into two analogous problems.

bmerry, though, has managed to avoid the geometric part almost completely! Here's his code: codeforces.com/contest/438/submission/6768704. Instead of checking that the triangle has valid diagonals as its sides, he just checks that the triangle is oriented correctly. Initially, this doesn't seem a sufficient condition, since the polygon is non-convex and thus even a correctly oriented triangle might intersect another side of the polygon. However, it turns out that in such cases there will be zero triangulations of the part that has a self-intersection. In other words, we'll find no way to find the next triangle some way down the dynamic programming. Is there an easy way to prove that?

Thanks for reading, and see you next week!