The IOI 2012 Competition

Hints for the second competition day's tasks

Ideal city

Simple solutions use Floyd-Warshall algorithm or iterated BFS on the unary-cost edges, and both require O(N) space: time is O(N^3) for Floyd-Warshall, and O(N^2) for the iterated BFS, which requires N times the number O(N) of edges.

A more efficient solution is the following one.

Last Supper

Let us first describe how to compute the optimal strategy of Leonardo in O(N log N) time.

For encoding the advice, the trivial solution would be to use N log K bits, i.e. log K for every color fault (i.e., every time the requested color is missing from the scaffold): this way we might specify exactly which color (within the K colors available on the scaffold) should be removed.

Here is an alternative encoding that uses only N+K bits and it is optimal in the worst case.

Jousting tournament

Solutions of various ranges of complexity are possible: all of them are essentially based on the trivial idea of trying all possible positions and simulating the tournament.

A trivial way to do that takes time O(N^3). We hereby describe a O(N^2)-time solution.

To go down to O(N log N) time we need to optimize the tree construction and the tournament’s simulations.