IOI archive
Each task folder keeps the copied write-up and implementation under a normalized solution.tex / solution.cpp pair for a consistent long-term archive.
Contest years
Archive entries
Hieroglyphs
Given two sequences A and B, find their universal common subsequence (UCS), or report that none exists.
Message
Each packet has 31 bits. Cleopatra controls exactly 15 positions (known to Aisha), while the other 16 positions are always transmitted correctly. Aisha must send a bit string M of length at most 1024, and Basma must r...
Mosaic
Given two arrays X[0..N-1] and Y[0..N-1] (with X[0] = Y[0]), define an N N grid where: Row 0: grid[0][j] = X[j] Column 0: grid[i][0] = Y[i] Otherwise: grid[i][j] = 1 if both grid[i-1][j] = 0 and grid[i][j-1] = 0; else...
Nile
Observation: adjacent pairing suffices After sorting artifacts by weight, every optimal matching pairs only adjacent elements. Suppose an optimal matching pairs artifacts a < b and c < d (in sorted order) with a < c <...
Sphinx's Riddle
We are given a connected graph with hidden vertex colours from \ 0,,N-1\ and one extra colour N that never appears initially. A query recolours some vertices and returns the number of monochromatic connected component...
Tree
Given a rooted tree with N nodes, each with weight W[i]. Assign integer ``coefficients'' C[i] to each node such that for every node i, the sum of coefficients in its subtree is between L and R (given per query). Minim...
Beech Tree
Necessary conditions [Distinct-color condition] If any node in the subtree has two children sharing the same edge color, the subtree is not beautiful. Suppose node u has children c_1, c_2 with the same color. When c_1...
Closing Time
Given a weighted tree, two special vertices X and Y, and budget K, choose closing times to maximize the total number of vertices reachable from X and from Y.
Longest Trip
Case D = 3: complete graph Every pair is connected, so any permutation of all N nodes is a Hamiltonian path. Case D = 2 Any three nodes span at least 2 edges. A Hamiltonian path always exists. Case D = 1: general When...
Overtaking
Key observation The reserve bus's presence does not affect the non-reserve buses' mutual blocking order among themselves. A slower non-reserve bus i only blocks the reserve bus if i arrived at the previous station str...
Soccer Stadium
Problem Statement Given an N N grid where some cells contain trees (F[r][c] = 1), find the largest regular stadium: a set of empty cells such that any two cells can be connected by at most two straight kicks (horizont...
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...
Candies
There are n boxes, each with capacity c[i]. There are q operations, where operation j adds v[j] candies to all boxes in range [l[j], r[j]]. If v[j] > 0, candies are added (capped at capacity). If v[j] < 0, candies are...
DNA
Given two strings a and b of equal length over the alphabet \ A, T, C\, answer queries: for a given substring range [l, r], what is the minimum number of swaps to transform a[l..r] into b[l..r]? If impossible, return -1.
Dungeons
There are n dungeons (indexed 0 to n-1) and a final dungeon n. Each dungeon i has: s[i]: opponent strength p[i]: strength gain if you lose w[i]: next dungeon if you win (w[i] > i) l[i]: next dungeon if you lose If you...
Keys
Given n rooms and m bidirectional corridors. Each room i contains a key of type r[i]. Each corridor j connects rooms u[j] and v[j] and requires a key of type c[j] to traverse. Starting from room i, you pick up the key...
Parks
There are n fountains at positions (x[i], y[i]) where all coordinates are even. Two fountains are adjacent if they differ by exactly 2 in one coordinate and are equal in the other. Build roads between adjacent fountai...
Registers
You have m = 100 registers, each containing b = 2000 bits. Register 0 initially contains n values, each k bits wide, packed consecutively. The remaining bits are 0. You must output the sorted values (or just the minim...
Biscuits
There are x bags to fill with biscuits. Biscuit type i has tastiness 2^i, and there are a[i] biscuits of type i available. Each bag must have the same total tastiness y. Count the number of distinct values of y that a...
Comparing Plants
Plants are arranged on a circle. The value r[i] describes the local ranking constraint for plant i inside the next k positions. For each query (x,y), we must decide whether every valid height assignment forces x to be...
Connecting Supertrees
Given an n n matrix p where p[i][j] \ 0, 1, 2, 3\, construct a simple undirected graph on n nodes such that the number of distinct simple paths between nodes i and j equals p[i][j]. If no such graph exists, report it....
Mushrooms
There are n mushrooms, each either type A or type B. Mushroom 0 is known to be type A. You can query a function use\_machine(x) that takes a sequence of mushroom indices and returns the number of adjacent pairs in the...
Stations
Given a tree with n nodes, assign labels from \ 0, 1,, n-1\ (all distinct, but need not match node indices) such that given only the labels of the current node s and target node t, plus the sorted list of labels of s...
Tickets
There are n colors and m tickets per color. Ticket j of color i has value x[i][j] (sorted in non-decreasing order within each color). There are k rounds. In each round, exactly one ticket from each color is used (each...
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.
Combo
A secret string S of length n is composed of characters from \ A, B, X, Y\. The function press(p) returns the length of the longest common prefix of S and the string p. Determine S using at most n+2 calls to press.
Highway Tolls
We are given a connected undirected graph with N vertices and M edges. Two hidden vertices s t were chosen. For each query we assign every edge weight A or B (A < B), and the grader returns the shortest-path distance...
Mechanical Doll
Build a switching network of binary switches (Y-shaped connectors called ``switches'') to route a ball through a sequence of triggers A_1, A_2,, A_m in order. Each switch has two outputs (X and Y) and alternates betwe...
Meetings
There are n mountains with heights H_0,, H_ n-1. For a query (L, R), choose a meeting point m [L, R] to minimize: cost(m) = _ i=L ^ R _ j [ (i,m), (i,m)] H_j. Return the minimum cost.
Seats
An H W grid has seats numbered 0 to N-1 (N = HW), each at a unique cell. A prefix \ 0, 1,, k-1\ is ``rectangular'' if these seats occupy a contiguous rectangular subgrid. After each swap of two seats, count the number...
Werewolf
For each query (S,E,L,R), determine whether there exists a vertex T such that: S can reach T using only vertices with index at least L; E can reach T using only vertices with index at most R. This is exactly the condi...
Books
There are n books on a shelf, forming a permutation P[0..n-1]. Book at position i should be at position P[i]. A librarian starts at position S and can move left or right, picking up and placing books. Each step costs...
Nowruz
This is an output-only task. We are given a grid with rocks (`\#') and free cells (`.'). We may turn some free cells into bushes (`X'). The remaining free cells must form a maze, i.e.\ for every two free cells there i...
Prize
There are several prize types, numbered by value. Type 1 is the unique diamond. If there are k prizes of type t-1, then there are strictly more than k^2 prizes of type t. For a query on position i, the grader returns...
Simurgh
We are given a connected graph. The hidden set of royal roads is a spanning tree. For one query we submit any spanning tree and receive how many of its edges are royal.
Train
A train travels on a directed graph with n nodes and m edges. Each node is either a ``charging station'' (good) or not. Each node is controlled by either player A or player B. Player A wants the train to visit chargin...
Wiring
We have red and blue points on a line. Each point must be incident to at least one wire of the opposite color, and the cost of a wire is the distance between its endpoints.
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...
Boxes
You are at position 0 on a circular track of length L with n boxes at sorted positions p_0 p_1 p_ n-1. You can carry at most K boxes at a time and must return to position 0 after each trip. Minimise the total distance...
Horses
Given arrays X[0..n - 1] and Y[0..n - 1] with X[i] 1, the profit from selling at year i is P(i) = Y[i] _ j=0 ^ i X[j]. Find _ 0 i < n P(i) 10^9 + 7, with point-update operations on X and Y.
Scales
Six coins have distinct weights forming a hidden permutation of \ 1, 2,, 6\. Available queries (each with 3 outcomes): getLightest(A,B,C), getMedian(A,B,C), getHeaviest(A,B,C): return the lightest/median/heaviest of t...
Sorting
Given a permutation S[0..n - 1] and a sequence of m grader swaps (P_i, Q_i), in each round i the grader first applies swap (P_i, Q_i) to S, then you apply your own swap (X_i, Y_i). Find the minimum number of rounds m^...
Teams
Each child i can join only teams whose size lies in [A_i,B_i]. For one query we are given team sizes K_1,,K_m and must decide whether the children can be partitioned accordingly.
Towns
We are given distances only between the N leaves of a weighted tree. Internal vertices are the large cities. We must find the hub radius R, and for the full task also decide whether some optimal hub is balanced: after...
Friend
A social network is built by adding people one at a time. Each new person i (i 1) has a ``host'' h_i (an existing person) and a protocol: IAmYourFriend (protocol 0): i becomes friends with h_i. MyFriendsAreYourFriends...
Game
You play the role of an interactor. A player asks queries of the form ``Is there an edge between u and v?'' about a hidden graph on n nodes. You must answer each query consistently (there must exist some valid graph m...
Gondola
A gondola system has n gondolas arranged in a circle, originally numbered 1, 2,, n. Over time, gondolas may break and be replaced: the k -th replacement gondola is numbered n + k. The circular order is preserved. Ther...
Holiday
There are n cities on a line, each with a number of attractions a_i. You start at city S (0-indexed) and have D days. Each day you either move to an adjacent city or visit the current city (collecting its attractions,...
Rail
There are n railway stations on a line, each of type C (``left-turn'') or type D (``right-turn''). Station 0 is type C at a known position. You may query the distance d(i,j) between any two stations. Using at most O(n...
Wall
A wall has n columns, each initially of height 0. Process q operations: Add(l, r, h): for each i [l, r], set height[i] (height[i], h). Remove(l, r, h): for each i [l, r], set height[i] (height[i], h). Output the final...
Art Class
Given an image (2D grid of RGB pixels), classify it into one of four categories: Class 1: Modern/abstract art (few colors, large uniform regions) Class 2: Paintings with distinct objects (moderate variation) Class 3:...
Cave
There is a cave with N doors (numbered 0 to N-1) and N switches (numbered 0 to N-1). Each switch controls exactly one door (a permutation), and each switch has a correct position (0 or 1) that opens its corresponding...
Dreaming
Given a forest (collection of trees) with N nodes and M edges (each with a weight), you can add edges of weight L to connect the trees into a single tree. Minimize the diameter (longest shortest path between any two n...
Game
Given a 2D grid of size R C (up to 10^9 10^9), support two operations: Update (r, c, v): Set the value at cell (r, c) to v. Query (r_1, c_1, r_2, c_2): Return the GCD of all values in the rectangle [r_1, r_2] [c_1, c_...
Robots
There are A ``weak'' robots (each with a weight limit X_i) and B ``small'' robots (each with a size limit Y_j). There are T toys, each with weight W_k and size S_k. A weak robot i can pick up toy k if W_k < X_i. A sma...
Wombats
Given a grid of R rows and C columns (R 5000, C 200), with horizontal edges (within each row) and vertical edges (between consecutive rows), each having a non-negative weight. Support two operations: changeH (r, c, w)...
Crayfish Scrivener
Implement a text editor with three operations: TypeLetter(c): Append character c to the current text. UndoCommands(u): Undo the last u commands, restoring the text to its state u operations ago. Undo can undo other un...
Ideal City
A city consists of N unit-square blocks on a grid (connected via shared edges). The distance between two blocks is the shortest path length through adjacent blocks. Compute the sum of pairwise shortest-path distances...
Jousting Tournament
There are N final positions, one of which will be occupied by the late knight of rank R. The other N-1 positions contain the ranks in array K in their original order. For each round i, the master removes the consecuti...
Last Supper
N people arrive in order, each preferring a color C[i] (from K possible colors). Chairs are numbered 0 to N-1. The advisor sees the full sequence C[0..N-1] and writes one advice bit per person. The assistant uses thes...
Odometer
A robot on an R C grid has two odometers: one counting horizontal moves and one counting vertical moves. Given a start and target position (with obstacles), find a path where the horizontal and vertical odometer readi...
Parrots
Encode a message of N 64 bytes into a multiset of integers in [0,255]. The decoder receives the integers in arbitrary order and must reconstruct the original message exactly.
Crocodile
A network of N chambers connected by M bidirectional corridors with travel times. Some K chambers are exits. A person starts at chamber 0. After choosing which corridor to take, a crocodile may block it, forcing the p...
Dancing Elephants
N elephants stand on a number line. A camera covers a contiguous interval of length L. Determine the minimum number of cameras to photograph all elephants. After each update (one elephant moves), recompute the answer.
Garden
A garden has N nodes and M edges (trails), each with a beauty value (lower index = more beautiful). From each node, you always take the most beautiful available trail. Because you cannot immediately backtrack, each no...
Hottest (Hot)
Given N measurement points in the plane, each at (x_i, y_i) with temperature t_i, find a circle of radius R that maximizes the average temperature of enclosed points. Output the center of such a circle.
Parrots
Encode a message of N 64 bytes into a multiset of integers in [0,255]. The decoder receives the integers in arbitrary order and must reconstruct the original message exactly.
Race
Given a tree with N nodes and weighted edges, find a path of total weight exactly K that uses the minimum number of edges. Output -1 if no such path exists.
Ricehub
There are R rice fields at sorted positions x_1 < x_2 < < x_R along a line. A hub can be placed at any integer position. The cost of connecting field i to a hub at position h is |x_i - h|. Given budget B, find the max...
Cluedo
This is an interactive problem modeled after the board game Cluedo. There are M murderers, W weapons, and L locations. The secret answer is a triple (m^*, w^*, l^*). In each query you guess a triple (m, w, l) and the...
Hotter Colder
An interactive problem on the integer line [1, N]. A hidden value X is fixed. Starting from position 1, each guess G receives a response: Hotter (+1): |G - X| < |P - X| where P is the previous guess. Colder (-1): |G -...
Language
Nature of the Task This is not a classical exact-algorithm task. It is an online classification problem: for each excerpt, we must guess one of 56 languages, then the grader reveals the correct answer and we may updat...
Memory
An interactive memory card game. There are 2N face-down cards forming N matching pairs. Each turn, flip two cards. If they match, they are removed. Otherwise, they are flipped back. The goal is to match all pairs usin...
Quality of Living
Given an R C grid where each cell has a unique quality rating from 1 to RC, find an H W subgrid whose median is minimized. The median of HW values is the HW/2 -th smallest value.
Saveit
Given a connected graph with N nodes (N 1000) and H hub nodes (H 36, nodes 0,, H-1), encode the shortest-path distances from every hub to every node into a bit string. The decoder must reconstruct all H N distances fr...
Traffic
Given a tree of N cities where city i has population p_i, find a city r such that when the tree is rooted at r, the maximum subtree population among r 's children is minimized. This node is called the traffic center.
Archery
Binary Search on Starting Position The key observation is that your final position after R rounds is a function of your starting target, and this function has structure that allows binary search (or a direct O(N N) ap...
Garage
This is a direct simulation. Maintain a set<int> of available spots (auto-sorted, smallest first). Maintain a queue<int> of waiting cars. Process each event: Arrival of car c: If a spot is free, assign the smallest; o...
Hiring
Key Observation Define the ratio r_i = S_i / Q_i. Worker i is eligible when c r_i. If we fix c = r_k for some worker k, all workers with r_i r_k are eligible, and the total cost is c Q_i = r_k Q_i. To minimize cost (a...
Mecho
Binary Search on Waiting Time [Monotonicity] If Mecho can escape after waiting t minutes, he cannot necessarily escape after waiting t+1 minutes (bees have spread further). Conversely, if he cannot escape at time t, h...
POI
Compute solvers[j] for each task j. For each contestant i: score[i] = _ j:solved (N - solvers[j]), tasks[i] = number of tasks solved. Sort by the given criteria and find P 's rank. Complexity Time: O(NT + N N). Space:...
Regions
Sqrt Decomposition Let B = N. A region is large if it has B nodes, small otherwise. There are at most N large regions. Case 1: r_1 is large. Precompute via DFS: maintain a counter of ancestors in r_1. At each node u o...
Rods
Greedy Approach Sort rods in decreasing order: a_0 a_1 a_ N-1. If there exist consecutive indices i such that a_i < a_ i+1 + a_ i+2, then all rods a_0, a_1,, a_ i+2 can form a polygon, and the answer is their total su...
Salesman
A salesman lives at position Y on a river (positions 1 to N). There are M fairs, each at a specific time, position, and profit. The salesman can attend any subset of fairs, but must attend them in chronological order....
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...
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.
Beans (Mexicane\ n
Linear Case (No Wrap-Around) Consider first the simpler problem where the beans are arranged in a line. Define: dp[i][0] &= maximum sum using beans 1,, i with bean i not selected, dp[i][1] &= maximum sum using beans 1...
Deciphering the Mayan Writing
Aho-Corasick Multi-Pattern Matching Build a trie from all patterns, recording which pattern ends at each terminal node. Compute failure links via BFS from the root: for each node u with child v on character c, the fai...
Forbidden Patterns (Writing)
Aho-Corasick Automaton + DP We build an Aho-Corasick automaton from all forbidden patterns and then run a DP over the automaton states. Build the automaton. Insert all forbidden patterns into a trie, then compute fail...
Pyramid
2D Prefix Sums Precompute the 2D prefix-sum array so that any rectangle sum can be queried in O(1): S[i][j] = _ r=1 ^ i _ c=1 ^ j grid[r][c]. Then: rectSum(r_1, c_1, r_2, c_2) = S[r_2][c_2] - S[r_1 - 1][c_2] - S[r_2][...
Birthday
Initially child i sits in seat i around a circle. We want the final circular order to be the given permutation, up to choosing one of the two possible orientations of that cycle. All children move simultaneously, and...
Garden (Largest Empty Rectangle)
Problem Statement Summary Given an R C grid with some cells blocked, find the area of the largest axis-aligned rectangle consisting entirely of unblocked cells. Solution: Largest Rectangle in Histogram Algorithm For e...
Mean Sequence
Problem Statement Summary The mean sequence of a_0, a_1,, a_N is b_0, b_1,, b_ N-1 where b_i = (a_i + a_ i+1)/2. Given the mean sequence b_0,, b_ N-1, find an original sequence of non-negative integers whose mean sequ...
Mountain
Problem Statement Summary Maintain a function f on discrete points \ 1,, N\, initially f(x) = 0. Support three operations: Range add: given l, r, v, set f(x) f(x) + v for x [l, r]. Clamp to zero: set f(x) (f(x), 0) fo...
Riv (Rivers)
Problem Statement Summary There are N villages arranged in a tree (rooted at village 0, which has a lumber camp). Each village v (for v = 1,, N-1) has: w_v: amount of wood produced, d_v: distance to its parent in the...
Rivers (Riv)
Problem Statement Summary There are N villages connected in a tree by rivers, with village 1 as the root (the main river outlet). Each village i (except the root) has a parent village p_i (the next village downstream)...
Artemis
Problem Statement Summary Given N points in the plane, find an axis-aligned rectangle containing the maximum number of points strictly in its interior (no point on the boundary). Solution: Sweep with Maximum Subarray...
Empodia
Key Insight Define c_i = a_i - i. If [l, r] is a framed interval with a_l = and a_r =, then a_r - a_l = r - l, which means c_l = c_r. Conversely, c_l = c_r is a necessary condition. An interval [l, r] is an ascending...
Farmer
Problem Statement Summary A farmer has N cows at known positions on a number line, and M barns (each with a capacity) also at known positions. Assign every cow to a barn (respecting capacities) so as to minimize the m...
Hermes
Problem Statement Summary Hermes starts at the origin and must visit N events in order. Event i is at position p_i on axis d_i \ X, Y\. He moves along both axes simultaneously: the time to go from (x_1, y_1) to (x_2,...
Phidias
Problem Statement Summary Given a rectangular marble slab of size W H (W, H 600) and N desired piece sizes (w_i, h_i), cut the slab by making full-width or full-height cuts (each cut traverses the entire current piece...
Polygon Triangulation
Problem Statement Summary Given a convex polygon with N vertices, each having a weight w_i, triangulate it (divide into N - 2 triangles using non-crossing diagonals) to maximize the total score. The score of triangle...
Amazing (Maze Exploration)
Problem Statement Summary This is an interactive problem. You are placed in an R C grid maze whose structure is unknown. At each step you can query which directions (N, S, E, W) are open from the current cell. Navigat...
Boundary (Convex Hull)
Problem Statement Summary Given N points (N 10^5) in the plane, compute the convex hull. Output the hull vertices in order, together with the perimeter, area, and the number of input points lying on the hull boundary....
Comparing Substrings
Problem Statement Summary Given a string S of length N (N 10^5) and Q queries (Q 10^5), each query specifies two substrings S[a a + -1] and S[b b + -1] and asks for their lexicographic ordering (equal, less than, or g...
Reverse
Problem Statement Summary Given a sequence of N integers and Q reverse operations, each specifying a range [l, r], apply all reversals in order and output the final sequence. A secondary variant asks for the minimum n...
Batch Scheduling
Problem Statement Summary There are N jobs (N 10, 000) to be processed on a single machine in the fixed order 1, 2,, N. Jobs may be grouped into consecutive batches. Each batch incurs a setup time of S before processi...
Bus Terminals
Problem Statement Summary Given N points (N 20, 000) in the plane, choose two terminal locations T_1, T_2 and assign each point to one of them so as to minimize the maximum Manhattan distance from any point to its ass...
Frog
Problem Statement Summary N stones (N 10^5) are arranged in a circle, numbered 1 through N. A frog sits on stone 1. Each jump, the frog advances exactly D stones clockwise. After each jump, the stone the frog lands on...
XOR
Problem Statement Summary Given an M N grid of 0s and 1s (M, N 500), find the largest-area subrectangle whose XOR (equivalently, the parity of its number of 1s) equals 1. Solution: 2D Prefix XOR Prefix XOR Define the...
Double Crypt
Problem Statement Summary A message is encrypted twice using two different simple ciphers, each parameterized by a key from a known key space: ciphertext = E_ k_2 (E_ k_1 (plaintext)). The key spaces for k_1 and k_2 e...
Ioiwari
Problem Statement Summary Ioiwari is a two-player game played on a triangular board with 10 cells arranged in a triangle of side 4: 0 1 2 3 4 5 6 7 8 9 Each cell initially contains a stone with a distinct value in \ 1...
Mobile Phones
Problem Statement Summary Maintain an S S grid (initially all zeros, S 1024) under two operations: Update(x, y, v): add v to cell (x, y). Query(x_1, y_1, x_2, y_2): return the sum of all cells in the rectangle [x_1, x...
Score
Problem Statement Summary Given a decimal number as a string of N digits and a budget of K adjacent swaps, find the maximum and minimum numbers obtainable. Leading zeros are not permitted (except for the number 0 itse...
Car Parking
Problem Statement A parking lot has N spaces. Cars are initially arranged in some configuration (a permutation with one empty space, denoted 0), and must be rearranged to a target configuration. Each move drives one c...
Palindrome
Problem Statement Given a string S of length N (N 5000), find the minimum number of characters that must be inserted (at any positions) to make S a palindrome. Solution Approach Key Observation The minimum number of i...
Post Office
Problem Statement There are V villages on a line at sorted positions x_1 < x_2 < < x_V. Place P post offices at village locations to minimize the total distance from each village to its nearest post office: _ i=1 ^ V...
Walls
Problem Statement A city contains N non-intersecting convex polygonal walls (possibly nested). A person must travel between a sequence of query points in order, walking around walls that block the direct path. Find th...
Code (Gray Codes)
Problem Statement Generate a Gray code of N bits: a cyclic sequence of all 2^N binary strings of length N such that consecutive strings (including the last and first) differ in exactly one bit. Solution Approach Refle...
Flower Shop
Problem Statement There are F flowers and V vases in a row (F V). Each flower i has a preference value pref[i][j] for vase j. Flowers must be placed in strictly increasing vase order: v_1 < v_2 < < v_F. Maximize the t...
Road Network (Tree Median)
Problem Statement Given a weighted tree with N nodes, find the node v that minimizes the sum of distances to all other nodes: S(v) = _ u=1 ^ N d(v, u). Output that node and the minimum sum. Solution Approach Rerooting...
Camelot
Problem Statement On an R C chessboard (R 30, C 26), there is one king and up to 63 knights. All pieces must gather at a single square. A knight may optionally pick up the king en route: it visits the king's square, c...
Contact
Problem Statement Given a binary string S of length n and integers a, b, k (1 a b 12, k 50), find the most frequently occurring bit patterns of length between a and b inclusive. Output the top k frequency groups (in d...
Picture
Problem Statement Given n axis-aligned rectangles, compute the total perimeter of their union. Only boundary segments separating the union's interior from the exterior are counted.: 1 n 5000, coordinates in [-10000, 1...
Polygon
Problem Statement A polygon-shaped game has n vertices labeled with integers and n edges labeled with + (addition) or * (multiplication). The vertices and edges alternate around the polygon: edge i connects vertex i t...
Mars Explorer
Problem Statement A robot navigates an n n grid where some cells are obstacles. Starting at (1,1), it must reach (n,n), return to (1,1), and go to (n,n) again --- three traversals total. On forward trips the robot mov...
Sentiment (Expression Evaluation)
Problem Statement Given a logical expression containing variables (single lowercase letters), the operators AND (\&), OR (|), and NOT (!), with parentheses for grouping, evaluate the expression for given variable assi...
The Buses
Problem Statement A person observes bus arrivals at a stop and records arrival times during an observation period. From these times, determine the bus routes (schedules). Each bus route is characterized by: A start ti...
Magic Squares
Problem Statement A 2 4 grid contains a permutation of the numbers 1 through 8, arranged in a cycle: 1 2 3 4 8 7 6 5 We store this linearly as positions s[0..7], where s[0..3] is the top row (left to right) and s[4..7...
Network of Schools
Problem Statement A network of n schools is connected by one-way links. Software distributed to a school propagates transitively along outgoing links. Task A: Find the minimum number of schools that must receive the s...
Sorting a Three-Valued Sequence
Problem Statement Given a sequence of n integers, each being 1, 2, or 3, sort the sequence in non-decreasing order using the minimum number of swaps. Each swap exchanges exactly two elements at arbitrary positions.: 1...
Packing Bits
Problem Statement Given a sequence of bits (0s and 1s) represented in a specific input format, pack them into bytes (groups of 8 bits) and output the result. format: First line: n, the total number of bits. Following...
Shopping Offers
Problem Statement A shop sells b different products (b 5). Each product i has a unit price c_i, and we wish to buy exactly q_i units of product i (q_i 5). There are s special offers (s 99). Each offer specifies a bund...
Wires
Problem Statement Given n points (terminals) in the plane, connect them all with wires of minimum total length. Each wire connects exactly two terminals, and all terminals must be connected (directly or indirectly). T...
The Circle
Problem Statement Given n integers arranged in a circle, you can remove adjacent pairs whose sum is divisible by a given number k. When a pair is removed, the neighbors of the removed elements become adjacent. The goa...
The Clock
Problem Statement There are 9 clocks arranged in a 3 3 grid. Each clock points to 12, 3, 6, or 9 (represented as 0, 1, 2, 3 respectively, where 0 means 12 o'clock). There are 9 possible moves, each of which rotates a...
The Triangle
Problem Statement Given a triangle of n rows of positive integers, find a path from the top to the bottom such that the sum of the numbers along the path is maximized. At each step, you may move to the element directl...
Day 1, Task 1: The Castle
Phase 1: Room Identification (Flood Fill) Two adjacent cells (r, c) and (r', c') are connected if no wall separates them. The wall bitmask makes adjacency checks direct: lll Direction & Neighbor & No wall if West & (r...
Day 1, Task 2: The Primes
Precomputation Generate all 5-digit primes via the Sieve of Eratosthenes (10000 to 99999). There are 8713 such primes. Filter to those with digit sum S. Typically 100 -- 400 remain. Build a prefix set: for each length...
Day 2, Task 1: Operations
BFS on the State Space This is a shortest-path problem in an unweighted graph where states are integers and transitions are the four operations. BFS finds the minimum number of steps. The key question is bounding the...
Day 2, Task 2: The School Bus
Two-Phase Bitmask DP For small n (up to about 15), we use an exact algorithm in two phases. Phase 1: Optimal Tour for Each Subset (Held--Karp TSP) For each subset S of locations whose total student count does not exce...
Problem 1: Points (Convex Hull)
Andrew's Monotone Chain Algorithm Sort all points lexicographically by (x, y). Lower hull: Scan left to right. Maintain a stack. For each new point, while the last two stack points and the new point make a non-left tu...
Problem 2: Teletext
Algorithm Load patterns: For each known character, store its h w pixel grid. Segment the image: Divide the input image into cells of size h w. Match each cell: Compare pixel-by-pixel against all patterns. For exact ma...
Problem 3: Islands
Single Water Level: Flood Fill Mark each cell as land if elevation[r][c] > L. Count connected components of land cells using BFS. Multiple Water Levels: Offline DSU To answer Q queries efficiently: Sort all cells by e...
Problem 1: Island
This is the classic connected-components-on-a-grid problem, solved by flood fill. Algorithm Iterate through every cell (i, j) in the grid. When an unvisited land cell is found, increment the island counter and perform...
Problem 2: Mangoes
This is a weighted interval scheduling problem. Each tree defines a job with interval [d_i, d_i + k - 1] and weight a_i. We must select a set of jobs (at most one per day) to maximize total weight. Greedy with Max-Hea...
Problem 3: Matrix Game
Minimax with Bitmask Memoization This is a two-player zero-sum game solved by minimax: State: A pair of bitmasks $(rowMask, colMask)$ indicating which rows and columns remain, plus a boolean for whose turn it is. Tran...
Problem 1: Subsets
We present two approaches: backtracking for small n and meet-in-the-middle for moderate n. Method 1: Backtracking (n 20) Enumerate subsets recursively, maintaining a running sum. At each position, either include or ex...
Problem 2: Map Labelling
2-SAT Formulation When each point has exactly two candidate positions, this is a classic 2-SAT problem: For each point i, define a boolean variable x_i: x_i = true means position 0, x_i = false means position 1. For e...
Problem 3: Festival Decoration
Feasibility Condition A valid arrangement exists if and only if _i c_i n 2. Necessity. In any valid arrangement of n elements, a single color can occupy at most every other position, i.e., at most n/2 positions. Suffi...
Problem 1: Packing Rectangles
Layout Enumeration There are exactly 6 topologically distinct ways to pack 4 axis-aligned rectangles into a bounding box. For rectangles labeled a, b, c, d with dimensions (w_i, h_i): Row: All four side by side. W = w...
Problem 2: Strings
Deriving the Recurrence Let f(n) denote the count of valid binary strings of length n. Partition these strings by their last character: a(n): valid strings of length n ending in 0. b(n): valid strings of length n endi...
Problem 3: Mobile
Recursive Computation The solution proceeds bottom-up. For each internal node with left subtree weight W_L and right subtree weight W_R, the balance condition d_L W_L = d_R W_R must hold. The minimal positive integer...
No IOI entries fit the current search and filter combination.