Editorial for IOI '11 P3 - Rice Hub
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 rice fields located at , the transportation cost from all these fields is minimized by placing the rice hub at a median. For example, when , the hub should be at , and when , placing it between and is optimal. In this problem, we will place the rice hub at for simplicity. Following this observation, we denote a solution by a sequence and let denote the length of , which is the solution's value (the number of rice fields whose rice will be transported to the hub). The cost of is , where is the -th element of .
Armed with this, we can solve the task by a guess-and-verify algorithm. We try all possible lengths of (ranging between and ). Next observe that in any optimal solution , the rice fields involved must be contiguous; that is, is necessarily for some . Therefore, there are solutions of length . For each choice of , we compute and the transportation cost in time and check if it is within the budget . This leads to an algorithm, which suffices to solve subtask 2.
To improve it to , we will speed up the computation of . Notice that we are only dealing with consecutive rice fields. Thus, for each , the cost can be computed in after precomputing certain prefix sums. Specifically, let be the sum of all coordinates to the left of rice field , i.e., and . Then, if , is given by , where . This algorithm suffices to solve subtask 3.
Applying a binary search to find the right length in place of a linear search improves the running time to and suffices to solve all subtasks.
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 , we add and find (1) , the best solution that uses only (a subsequence of) the first rice fields (i.e., ), and (2) , the best solution that uses only (a subsequence of) the first rice fields and contains . This can be computed inductively as follows. As a base case, when , both and are just and cost , which is within the budget . For the inductive case, assume that and are known. Now consider that is appended with , denoted by , if the cost is at most , or otherwise it is the longest prefix of that costs at most . Furthermore, is the better of and . To implement this, we represent each by its starting point and ending point ; thus, each iteration involves incrementing and possibly , but is always at most . Since takes to compute, the running time of this algorithm is and suffices to solve all subtasks.