Tuesday, May 20, 2014

This week in competitive programming

The last week had two tournament rounds. On Saturday, TopCoder Open 2014 Round 2A took place (problems, results, top 5 on the left, my screencast). What does "2A" mean? TopCoder has changed the format for the TopCoder Open two years ago. In 2011, the online elimination rounds were structured in a relatively straightforward way: 2000 participants from the qualification round participated in Round 1, and 850 of them advanced to Round 2. Out of 850 participants of Round 2, the best 350 advanced to Round 3. In the same manner, 150 advanced to Round 4, 60 advanced to Round 5, and 24 advanced to the onsite finals.

In other words, in order to qualify for the onsite round one had to place in top 30% of all participants five times. That usually translated to carefully checking and rechecking one's solutions being the most important aspect of the competition for the top algorithmists. Taking risks and performing exceptionally was not rewarded too much.

The format has changed completely starting from 2012. Now 2500 participants from the qualification round (which is now called Round 1A/1B/1C) can participate in three more rounds: 2A, 2B and 2C. In each of those rounds almost 2500 people can participate, and only 50 advance to Round 3 - just the top 2%! If you fail to advance from Round 2A, though, you can participate in the Round 2B, and possibly 2C if still needed. The 150 best competitors determined this way participate in rounds 3A and 3B, with 12 best participants from each round going to the onsite finals - this time the top 8% from each round. The onsite finals have 24 participants, just like in 2011.

There are still five rounds that select 24 best algorithmists from 2000+ participants. In the best case, though, one can participate in just two of them and advance to the onsite round. In my view, such sharp elimination percentages push people to take risks and do their best, and the competition becomes more exciting. My own chances for making the onsite finals have probably reduced, since consistency was always my strength and played nicely with the old system. The new system also allows for more interesting and challenging problems since the cutoff is higher.

The medium problem in this year's Round 2A is quite interesting to reason about: there are 50 wolves on a line segment of length L, i-th wolf starting from point ai and going to point bi. This sounds relatively simple - but the wolves are not allowed to pass each other anywhere except the ends of the segment. So if two wolves want to swap, they have to go either to the leftmost point of the segment, or the rightmost point of the segment. What is the minimum total travel distance they can travel in order for all of them to reach their destinations?

On Sunday, the second Qualification Round of the Russian Code Cup took place (problems, results, top 5 on the left). As I understand, the new Russian Code Cup website ran smoothly this time and the competitors could concentrate on solving the problems - congratulations to the organizers on overcoming all difficulties!

Thanks for reading, and see you next week!

No comments:

Post a Comment