IOI 2004

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

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

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

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

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

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