Thursday, November 20, 2014

TCO 2014 Algorithm Finals day

TopCoder Open 2014 Finals have concluded earlier today (results with statements accessible by clicking the point value, top 5 on the left). Gennady has completed his full sweep of 2014 trophies, while I came in second place. Looking back at how the contest went, there were several ways I could've squeezed the first place:
  • I could've solved the 1100. This is the most obvious way, and yet the most difficult since it's still not clear to me how long the solution would take to write. The problem itself had very simple and beautiful statement: given the integer scores of N (up to 500000) teams, calculate the number of possible rankings if the score of each team either stays the same or increases by exactly 1, and ties a broken by the team number. The basic idea for the solution is also quite straightforward: there are 2N ways to either add 1 to each score or not, and it takes quite specific conditions for two different sets of scores to lead to the same ranking, so we should carefully avoid counting those specific cases. However, the devil is in the details - I had most code ready by the end of the coding phase, but it's still not clear how long it would take to debug it. Because of that, we don't know if opening the 1100 earlier would've lead to better or worse results, so we can't tell which strategy was better this time :)
  • I could've found one more challenge than Gennady. I've actually found the issue in bmerry's 550, but somehow hesitated to challenge, which was clearly a mistake. But in order to find the second challenge I had to beat Endagorion or tourist on one of the 350 challenges, and it was quite hard since I was reading the 350s in the wrong order: from highest score to lowest.
  • I could've spent less time on the 550. Somehow analyzing the problem on paper took a very long time, even though there was no algorithmic difficulty: the standard approach for solving such problems, considering what happens if we swap two adjacent instances, worked very well.

(Picture on the left from the TopCoder website: spectators are watching the coding phase)

Well, better luck next time :) Misof has written his awesome commentary for the finals, go check it out! And of course, check back in the beginning of next week for the weekly summary.

No comments:

Post a Comment