IOI 2009

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

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

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

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

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

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

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

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