- 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.
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