IOI 2015
All 6 IOI tasks from 2015, 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.
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...