Living in NlogN World

The IOI 2009 is over and a new champion has arise. This time is Henadzi Karatkevich, a 14 years old kid from Belarus. Yeap, you're reading well, only 14 years old.

The problems of this years were 8 instead of the traditional set of 6 problems. Even more impressing is the fact that the solution for full score of most of the problems were O(NlogN). 6 out of 8 problems in total. The other two were about simulation and DP, very easy in fact...

You may be used to solve problems with "small" constraints, but this year IOI was for those who are not used to solve problems with really huge constraints. It was common to find constraints as N<(500.000, 1.000.000, 1.000.000.000) and their naive solution is O(N^2), O(N^3) or O(2^N). So, how the problems were solved for full score? Two main techniques were used:

• Sorting
• Binary Search

The idea behind each problem is the following:

Day 1:

• Archery: Binary Search with "simulation" (this was the hardest problem in the competence)
  
• Hiring: Sorting/Heap
• Poi: Sorting (one of the easiest problems in the competence)
• Raisins: DP, with a precalculation like Maximum Sum (UVa 108)

Day 2:

• Garage: Simulation (this one was other really easy problem)
• Mecho: BFS with Binary Search
• Regions: Disjoints Sets/DFS/Trees
• Salesman: Sorting (hard problem)

I'm still studying the solutions for Archery, Hiring and Salesman, because their solution is not trivial at all. In fact, Archery did not get any perfect score in the whole competence. The other problems are not big deal if you have knowledge in their solution techniques.

If you want to check the problems by yourself, go here.

Happy weekend for all of you!