IOI 2008
All 5 IOI tasks from 2008, organized as individual solution pages.
Problem set
Each entry below goes straight to the public problem page, with the statement, editorial, code, and raw resources kept together.
Fish
Independence Across Species The validity constraint is independent across species: for each species, we require / 2 within that species, regardless of other species. Therefore: (valid subsets including empty) = _ t=1...
Islands
Structure of Functional Graphs Each connected component of a functional graph contains exactly one cycle. Nodes not on the cycle form trees rooted at cycle nodes (the ``rho'' shape). Algorithm For each connected compo...
Linear Garden
Precompute Valid Completions Define F[ ][b] = number of valid binary sequences of length starting from balance b, such that the balance stays within [-K, K] at every step. Recurrence: F[ ][b] = F[ -1][b+1] + F[ -1][b-...
Pyramid Base
Binary Search on Side Length [Monotonicity] If a square of side s can be placed with cost B, then any square of side s' < s can be placed at the same position with cost B (it overlaps a subset of the same obstacles)....
Type Printer
Trie + DFS Build a trie from all N words. Each trie edge corresponds to a Push (descending) or Pop (ascending). Each terminal node requires a Print operation. A DFS traversal visits every edge twice (down and up), exc...