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!

No comments:

Post a Comment