Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak
Sortings, ternary-search, minimizing function
For a given set of N segments, all of length L, where S_i denotes the left endpoint of the i-th segment, and two points A \leq B, the goal is to place all N segments inside the range [A, B] in such a way that endpoints of segments have integer coordinates, no segments overlap in points other than their endpoints, and there is no uncovered space between any two consecutive segments. We want to find the minimum cost to do that, where the cost is the sum for all segments of distances between their initial and final positions. It is guaranteed that range [A, B] is large enough to contain all N segments.
The first observation is to notice that the final placement of the segments can be uniquely identified by integer x, denoting the left endpoint in the final position of the left-most of the segments.
The second observation is that if we consider two left endpoints of the different segments, S_i < S_j, then in a final optimal position, the left endpoint of the i-th segment will be also to the left of the left endpoint of the j-th segment. This is somehow intuitive, and one can prove it by considering the positions of S_i, S_j and x in a fixed final position. From now, we assume that the segments are given in the sorted order, i.e. S_i \leq S_j for i < j.
Thus, we want to find such integer x, the left endpoint of the left-most of the segments, which minimizes the function:
The crucial observation is to notice that this function is weakly unimodal function, which means in this problem, that there exists a value m, such that for x \leq m, f(x) is weakly monotonically decreasing, and for x \geq m, f(x) is weakly monotonically increasing. For such functions, we can use ternary search to find their extremum (in this case minimum) value. For the lower bound of ternary search, we set A, and we set B-N \cdot L as the upper bound. Since computing the value of f(x) for a fixed x takes O(N) time, the total time complexity is O(N \cdot \log(B-N \cdot L - A)).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.