Tuesday, November 18, 2014

This week in competitive programming

Open Cup 2014-15 Stage 3 was the only contest of the week (results, top 5 on the left). The Tapirs team from the Moscow State University have shown once again that the ITMO 1 team is not impossible to beat this year. Congratulations!

Problem B was a beautiful exercise of combining several well-known ideas into a good solution. You were given a road network of some mythical country represented as an undirected graph with at most 200000 nodes and edges, with each edge having a length in kilometers. Some nodes were special — they contained petrol stations. Then, you were given a series of at most 200000 requests of the form "Is it possible to get from node A with a petrol station to node B with a petrol station using a car that is capable of traveling at most C kilometers without refueling?" for different values of A, B and C. Can you answer all those requests using just 2 seconds of CPU time in total?

Late on Sunday, the TopCoder Open 2014 (official blog, official photos) started in San Francisco. You can see the introductory video to the left, configured to start right where TopCoder Open victories are compared to the Moon landing :) But you can of course watch it from the beginning, it's just over 1 minute in length.

The organizers have decided to take advantage of the nicely competitive algorithm competition format, and added several more algorithm rounds to entertain the spectators. On Sunday, the Celebrity Algorith Match gathered 8 past greats. Each competitor has nominated a charity, and the charity of the winner would get the $10000 prize. You can guess the winner from the picture on the left :)

Four "Pickup Algorithm Rounds" where all spectators can participate are also on the schedule. I guess the original idea might've been to get the spectators from the "outside world" interested in algorithmic programming contests, and it's working to some degree as people with completely new TopCoder handles are taking part. The top of the standings, however, is still taken by people with "target" rating working for different companies in the Bay Area :)

Monday is the Marathon day, with 12 finalists competing for 12 hours trying to design the best possible route for a plane putting out a forest fire. You can pretty much understand the problem from this video showing one of the solutions at work. The current standings change often, and the margins are not too slim, suggesting that the final round problem was once again picked perfectly: enough ideas to explore in 12 hours, yet very easy to get going and with wonderful visualization. Great job!

Thanks for reading, and check back tomorrow for the news about Algorithm semifinals. Please ask any questions you might have about the TCO in comments!

No comments:

Post a Comment