Editorial for IOI '11 P3 - Rice Hub


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The key insight to solving this problem is the observation that for any K rice fields located at r_0 \le r_1 \le \dots \le r_{K-1}, the transportation cost from all these K fields is minimized by placing the rice hub at a median. For example, when K = 1, the hub should be at r_0, and when K = 2, placing it between r_0 and r_1 is optimal. In this problem, we will place the rice hub at r_{\lfloor K/2 \rfloor} for simplicity. Following this observation, we denote a solution by a sequence S \subseteq \langle r_0, \dots, r_{R-1} \rangle and let |S| denote the length of S, which is the solution's value (the number of rice fields whose rice will be transported to the hub). The cost of S is cost(S) = \sum_{r_j \in S} |r_j-h(S)|, where h(S) is the \left\lfloor \frac{|S|}{2} \right\rfloor-th element of S.

An \mathcal O(R^3) solution

Armed with this, we can solve the task by a guess-and-verify algorithm. We try all possible lengths of S (ranging between 1 and R). Next observe that in any optimal solution S^*, the rice fields involved must be contiguous; that is, S^* is necessarily \langle r_s, r_{s+1}, \dots, r_t \rangle for some 0 \le s \le t \le R-1. Therefore, there are R-K+1 solutions of length K. For each choice of S, we compute h(S) and the transportation cost in \mathcal O(|S|) time and check if it is within the budget B. This leads to an \mathcal O(R^3) algorithm, which suffices to solve subtask 2.

An \mathcal O(R^2) solution

To improve it to \mathcal O(R^2), we will speed up the computation of cost(S). Notice that we are only dealing with consecutive rice fields. Thus, for each S, the cost cost(S) can be computed in \mathcal O(1) after precomputing certain prefix sums. Specifically, let T[i] be the sum of all coordinates to the left of rice field i, i.e., T[0] = 0 and T[i] = \sum_{j=0}^{i-1} X[j]. Then, if S = \langle r_s, \dots, r_t \rangle, cost(S) is given by (p-s)r_p-(T[p]-T[s])+(T[t+1]-T[p+1])-(t-p)r_p, where p = \lfloor \frac{s+t}{2} \rfloor. This \mathcal O(R^2) algorithm suffices to solve subtask 3.

An \mathcal O(R \log R) solution

Applying a binary search to find the right length in place of a linear search improves the running time to \mathcal O(R \log R) and suffices to solve all subtasks.

An \mathcal O(R) solution

We replace binary search with a variant of linear search carefully designed to take advantage of the feedback obtained each time we examine a combination of rice fields. In particular, imagine adding in the rice fields one by one. In iteration i, we add r_i and find (1) S^*_i, the best solution that uses only (a subsequence of) the first i rice fields (i.e., S^*_i \subseteq \langle r_0, \dots, r_i-1 \rangle), and (2) S_i, the best solution that uses only (a subsequence of) the first i rice fields and contains r_i-1. This can be computed inductively as follows. As a base case, when i = 0, both S_i and S^*_i are just \langle r_0 \rangle and cost 0, which is within the budget B \ge 0. For the inductive case, assume that S^*_i and S_i are known. Now consider that S_{i+1} is S_i appended with r_i, denoted by S_i \cdot r_i, if the cost cost(S_i \cdot r_i) is at most B, or otherwise it is the longest prefix of S_i \cdot r_i that costs at most B. Furthermore, S^*_{i+1} is the better of S^*_i and S_{i+1}. To implement this, we represent each S_i by its starting point s and ending point t; thus, each iteration involves incrementing t and possibly s, but s is always at most t. Since cost(\langle r_s, \dots, r_t \rangle) takes \mathcal O(1) to compute, the running time of this algorithm is \mathcal O(R) and suffices to solve all subtasks.


Comments

There are no comments at the moment.