IOI 2007
All 6 IOI tasks from 2007, 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.
Aliens
Simultaneous 2D Binary Search Each query at (x, y) reveals the quadrant containing the target, which narrows the search space in both dimensions simultaneously. Maintain a bounding box [lo_x, hi_x] [lo_y, hi_y], initi...
Flood
Coordinate Compression and Expanded Grid The standard technique for planar subdivision problems: Compress coordinates. Collect all distinct x - and y -values. Each compressed cell (i, j) represents the rectangular reg...
Miners
DP Formulation The bonus at a mine depends only on its last two deliveries (plus the new one). Encode the state as (a_1, a_2, b_1, b_2) where a_1, a_2 are the last two deliveries to mine 1 and b_1, b_2 to mine 2. Each...
Pairs
Given N animals on a board of dimension B \ 1,2,3\, count unordered pairs whose Manhattan distance is at most D.
Sails
Key Insight: Convexity and Greedy Since c 2 is a convex function of c, the sum c_k 2 is minimized when the c_k values are as equal as possible. Therefore, for each mast we should place sails at the heights that curren...
Training
The graph consists of a tree plus additional non-tree edges, each with a removal cost. We want to delete a minimum-cost set of non-tree edges so that the remaining graph contains no even cycle.