Tuesday, July 29, 2014

This week in competitive programming

TopCoder SRM 628 took place on Tuesday (problems, results, top 5 on the left). The TopCoder admins are having a hard time finding good problems, so they've ran just two SRMs this month instead of the usual four. I've skipped this round, while Gennady didn't, and he has claimed the first spot in the overall TopCoder rating as the result after winning this round - congratulations!

On Saturday, there was another TopCoder round - TopCoder Open 2014 Round 3A (problems, results, top 12 on the left, my screencast). Just 12 people advanced to the onsite finals in San Francisco, all listed on the left - congratulations to all! I've managed to squeeze out the first place in the last seconds by submitting a heuristic solution for the hard problem (TopCoder login required to view it). I want to discuss my solution in a separate post later this week, but in the meantime, here's what the problem was about: you were given at most interesting 50 points on a line that you need to visit in any order starting from point 0. In addition to moving along the line at one unit per second, you can use teleports between the given pairs of locations. The teleports are non-interleaving (if one teleport connects points a < b, and the other connects points c < d, then either b < c or d < a), and there are at most 25 teleports, each taking exactly one second to use. What's the shortest time required to visit all interesting points?

On Sunday, Codeforces ran MemSQL Start[c]UP 2014 Round 1 (problems, results, top 5 on the left). The round featured one quite technical problem that highlighted a flaw in my preparations: problem E required a suffix structure, like a suffix tree, a suffix array or a suffix automaton to be solved. While I do know in theory how all of those work, using them in practice is always painful for me and takes a lot of time. The reason for that is mostly the fact that those data structures were quite new back when I was actively learning new things in competitive programming, and I haven't caught up with the recent developments in the area. I can definitely do better - and this contest is another good reason to actually figure those data structures out and be ready to use them.

The problem went like this: you are given three strings of total length up to 300000. For each length L, how many triplets of substrings of these three strings exist such that all three substrings are equal and have length L? If a substring appears several times in a string, its occurrences are counted separately.

Thanks for reading, and check back next week!

Monday, July 21, 2014

This week in competitive programming

As advertised, the week started with IOI 2014 (problems, results, top 5 on the left). I like the problem "Game" a lot, since it's both interesting to solve and has a very simple but unusual setting. Two players are playing a game on N vertices. On each turn, the first player picks a pair of vertices, and the second player has to either draw an edge connecting them, or declare that there's no edge connecting them. The first player asks about each of N*(N-1)/2 pairs exactly once, and his goal is to figure out whether the graph will be connected after the game ends; the second player's goal is to keep the connectedness (ugly word, but is there a better choice?) of the graph unknown until the very last answer. N is up to 1500, time limit for the entire game is 1 second.

IOI and other high school competitions are well-known for tasks where the contestant has to implement one player of a game, and the judges provide the other player. However, a usual setting in games like this one would be for the competitor to be the player asking questions, and the jury to be the player giving answers - but in this case it's exactly the opposite: the contestant had to implement a strategy for the second player that would always win. Can you see such strategy?

The problems in general turned out a bit too easy, and did not allow to determine the single winner - three competitors solved all of them. Congratulations Scott, Ishraq and Yinzhan! (Scott did stand out by achieving the perfect score just 2 hours into the first day and just 3 hours into the second day)

On the weekend, Codeforces Round 257 gathered a big crowd of 3000+ participants (problems, results, top 5 on the left). Congratulations to semiexp on the victory!

Thanks for reading, and check back next week!

Monday, July 14, 2014

This week in competitive programming

Last week was a classical one, with just a TopCoder round and a Codeforces round. TopCoder SRM 627 took place on Thursday (problems, results, top 5 on the left, my screencast). I've enjoyed solving the hard problem a lot - the idea of reducing the problem to maximum flow was natural, but actually figuring out the reduction was a very interesting process. Can you see the reduction?

The problem, in short, is as follows: you're given a 50x50 grid of characters. Some of the characters are towers, while the rest are enemy units. Each tower is pointed into one of four cardinal directions, and it's guaranteed that there are no other towers in that direction. Each enemy unit has an associated cost - an integer between 0 and 9. We have to pick at most one enemy unit for each tower in such a way that the tower 'sees' the unit according to its direction, and that the segments connecting the tower with its enemy unit do not intersect or touch. What is the maximum possible total cost of the chosen enemy units?

Congratulations to Gennady for being the fastest to solve this nice problem, and for the resulting SRM win!

The weekend featured Codeforces Round FF (problems, results, top 5 on the left, my screencast). For the second time in a row, we have five different flags in top 5, and Adam (subscriber) is there - but this time he's only second, and Vlad has won convincingly as the only one to solve four problems. Congratulations!

I don't usually cover marathon competitions, but this looks like a good moment to touch base: the selection for TCO 2014 Marathon has concluded this week, and we have 12 finalists (list). It's amazing to see 8 of the last year's finalists advance again this year, despite the incredibly tough selection system and the variety of problems that the marathoneers enjoy. Congratulations to all finalists!

For those not familiar with marathon competitions - those are the contests where there's just one very tough problem to solve and several days or weeks to solve it. There's usually no single ideal or "correct" solution, and the contestants are scored based on how good their solutions perform on a hidden test set.

Next week is promising an interesting switch from the TopCoder/Codeforces routine: the International Olympiad in Informatics 2014 is taking place in Taiwan. This is the highest level of competition for secondary school students, and also probably the most prestigious algorithmic competition that is not ran by a private company: it is ran by United Nations via UNESCO.

Pavel, the coach of the Russian team, has promised a Russian blog about the olympiad (one of his pictures is on the left). There will probably be some information in English on the official website. Please share other blogs writing about the olympiad in comments!

And of course, check back next week for the IOI results!

Sunday, July 6, 2014

This week in competitive programming

The final chance to hop onto the TCO train was on Saturday: TopCoder Open 2014 Round 2C (problems, results, top 5 on the left). The final 50 competitors who will battle for the chance to get to the onsite finals in San Francisco were selected, and here's the entire set of 150 Round 3 participants. Congratulations to Vladislav on winning the round!

At the same time, the 100 best contestants who have already advanced to Round 3 could participate in the elite Parallel Round 2C, but only 19 chose to do so (results, top 5 on the left). Egor won the parallel round with a big margin (I usually think of the margins on TopCoder in challenges, so his margin was 3+ challenges), and he was also faster than Vladislav from the main round.

And finally, Codeforces Round 254 took place on Sunday (problems, results, top 5 on the left). It was the first time we have five different flags in top 5 since March, and Adam got the first place - congratulations!

I've skipped this week's rounds because I was taking some rest during the weekend, and want to share some nice views that I've enjoyed instead of participating in TopCoder and Codeforces:

Thanks for reading, and see you next week!

Sunday, June 29, 2014

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!

Wednesday, June 25, 2014

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!

Tuesday, June 24, 2014

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.