IOI 2016
All 6 IOI tasks from 2016, 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
On an m m grid, n points of interest must be covered by at most k axis-aligned square photos whose diagonals lie on the main diagonal. The cost of a side- s photo is s^2. Overlapping areas between consecutive photos m...
Messy
Given n (a power of 2), determine an unknown permutation P of \ 0, 1,, n-1\ in two phases: Phase 1 (Add): Insert binary strings of length n into a set S. Shuffle: P is applied to every string in S (bit i moves to posi...
Molecules
Given n molecules with weights w_1, w_2,, w_n and a target range [l, u], find a non-empty subset whose total weight is in [l, u], or report that none exists. A key constraint: u - l w_ - w_.
Paint
A 1D grid of n cells is to be painted. Some cells are known to be black (X), some white (\_), and some unknown (.). You are given k clues: the lengths of consecutive black segments from left to right. Determine for ea...
Railroad
A roller coaster has n sections. Section i has a starting speed s_i and an ending speed t_i. To connect section i to section j: If t_i s_j: free (braking is free). If t_i < s_j: costs s_j - t_i (need to accelerate). F...
Shortcut
A caterpillar tree is a path graph (the ``spine'') with additional pendant edges (``legs''). Each vertex has a position on the spine and possibly a leg length. You can add one shortcut edge of cost c between any two s...