IOI 2005

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...

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...

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...

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...

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...

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)...