IOI 2019
All 6 IOI tasks from 2019, 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.
Arranging Shoes
There are 2n shoes: n left shoes (represented by -i) and n right shoes (+i) for sizes i = 1,, n. Rearrange using the minimum number of adjacent swaps so that each pair is adjacent with the left shoe on the left.
Rectangles
Given an n m grid of distinct integers, count rectangles (r_1, r_2, c_1, c_2) with r_1 < r_2, c_1 < c_2 such that every boundary cell is strictly greater than every interior cell.
Sequence (Line)
Given an array of n integers, find the minimum number of elements to change so the result is an arithmetic sequence a + bi for positions i = 0, 1,, n-1.
Sky Walking
Buildings are vertical segments, skywalks are horizontal segments, and movement is allowed only along those segments. We want the shortest path from the bottom of building s to the bottom of building g.
Split the Attractions
Given a connected graph with n nodes and m edges, partition the nodes into three groups of sizes a, b, c (a + b + c = n) such that each group induces a connected subgraph. Output the assignment or report impossibility.
Vision
An H W grid has exactly two cells set to 1. Construct a circuit of AND, OR, XOR, NOT gates that outputs 1 iff the Manhattan distance between the two cells equals K.