IOI 2022
All 6 IOI tasks from 2022, 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.
Catfish Farm
Column DP formulation We process columns left to right. Define dp[c][h] = maximum total weight considering columns 0,,c with h_c = h. Transition When transitioning from column c-1 with height h_ prev to column c with...
Digital Circuit
Per-gate counting For each threshold gate i with c_i inputs, if exactly k of its inputs output 1, then exactly (k, c_i) choices of p_i make gate i output 1, and c_i - (k, c_i) make it output 0. Aggregation with genera...
Insects
Step 1: Count distinct types Insert insects one by one. After each insertion, if press\_button() > 1, remove the insect (it is a duplicate). The number of insects remaining in the machine equals the number of distinct...
Prisoner Challenge
Ternary narrowing Each whiteboard state encodes a pair (which bag to inspect next, current uncertainty interval [, r]). Initially [, r] = [1, N]. The prisoner inspects the designated bag and sees value v: If v <: the...
Radio Towers
Characterization A set S = \ s_1 < s_2 < < s_m\ [L,R] is mutually communicating with parameter D if and only if every consecutive pair (s_i, s_ i+1) can communicate. The ``only if'' direction is trivial. For ``if'': t...
Thousands Islands
Key observations Since every node has out-degree 1, any walk from node 0 must eventually revisit a node (by pigeonhole), producing a cycle. If node 0 itself lies on such a cycle, traversing it twice gives a valid jour...