Informatics Olympiad Solver

IOI 2011 • TASK 3: RICE HUB

C++ & Python Verified
Day 1 Task 3 Difficulty: Medium-Hard

Rice Hub (Riceway)

In the countryside there is a straight road called the Rice Way along which there are R rice fields. Each field i is located at coordinate X[i], where 1 ≤ X[0] ≤ X[1] ≤ ... ≤ X[R-1] ≤ L.

We want to build a single Rice Hub at some coordinate H. We have a transport budget B. The cost to transport one truckload of rice from field i to the hub H is |X[i] - H|.

Goal: Strategic Placement

Your program must find the maximum number of fields from which we can transport rice to a single hub location without exceeding our budget B.

Input constraints

Number of fields (R)

1 to 100,000

Max Coordinate (L)

1 to 1,000,000,000

Budget (B)

0 to 2 × 1015

Coordinates (X[i])

Sorted integers

Grading Subtasks

Subtask 1 (17 Points): R ≤ 100, L ≤ 100, B ≤ 1,000 O(R3) or O(R2)
Subtask 2 (25 Points): R ≤ 5,000, B ≤ 1012 O(R2)
Subtask 3 (26 Points): R ≤ 100,000, B ≤ 1015, L ≤ 1,000,000 O(R log R) or O(R)
Subtask 4 (32 Points): No additional constraints Optimal O(R)

Time Complexity

O(R)

Sliding window right pointer j scans from left to right. Left pointer i moves monotonically forward. Total pointer advances ≤ 2R.

Space Complexity

O(R)

Requires a prefix sum array of size R + 1 to support constant time $O(1)$ sum coordinate queries.