This is the first of a series of blog posts about the task `meetings' from IOI18. It is also available in a contest that will take place in conjunction with these posts.
We chose this problem as an experiment to see whether we can present a single problem in a way that it covers a lot of useful knowledge for a contest related topic. In this aspect, meetings is a great task in that it starts with dynamic programming, then moves into range queries and tree constructions, and finally, finishes it off with geometric data structures.
Furthermore, the setting of meetings is as classical as a data structure problem can get: you get a static array, and you query about some statistic on its subintervals. This is a setting that has been viewed as "completely understood" by most competitors who aim for top 40 or higher at the IOI since around 2005. However, this problem was given, and had 0 solvers. I've also heard several past contestants who placed in the Top-3 at IOIs refer to this problem as "Godly", so that's another reason to discuss it in more details.
In short, the ideas underlying meetings are extremely novel, especially given how well understood the topic is. Also, if mechanically you can solve meetings in 2 hours reliably, you shouldn't have trouble with most data structural topics.
Continue reading...
