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!

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!

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!

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!