CONSESNK - Editorial

Editorialist: Pawel Kacprzak

Easy

PREREQUISITES:

Sortings, ternary-search, minimizing function

PROBLEM:

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.

EXPLANATION:

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:

f(x) = \sum\limits_{1 \le i \leq N} |x + (i-1) \cdot L - S_i|

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.

This can be solved without using ternary search.
If we try to plot f(x) with x , we will observe that the minima occurs at the median value of S[i]-i.L (for odd value of N) and between the two medians (inclusive) for even value of N. The function will be increasing monotonic to the right of minima and decreasing monotonic to the left of minima.
All we have to do now is check whether minima lies in the range [a,b-N.L] or to the left or right of it.

The overall complexity of this solution is O(N.logN)

You can find my implementation of this here : Solution

7 Likes

Any simple o(n) solution…

Can someone tell me why I’m getting wrong answer using ternary search. Here is the link to my

“The crucial observation is to notice that this function is weakly unimodal function”

Can you prove this statement? It seems intuitive but I would like a proof to back it up

Is there any simple O(n) solution

why in this problem if we take first all the left snakes then the snakes which are in interval(A<=Si<=B) then take right to the B snakes is giving wrong answer.

can somebody provide the test case?

if the link is not working, you can use this link for the editorialist’s solution

one more think i would like to add, the function f(x) runs from i=0 to i=n-1.
if we use i=1; i<=N, then logically it’s not right because for the first S[i] f(x) should be | x + 0*L -S[0] |, think over it you’ll understand.

How can we prove that f(x) is weakly unimodal function?

@pkacprzak How is that function f(x) generated? I mean, how is it arrived at?

@sahil_g, Actually we could have O(N) in average if to use quick select for finding the median element.

my program has passed both the test cases but giving wrong when i submit it… Can anyone please help me? I think i have missed something…

why am I getting TLE? https://www.codechef.com/viewsolution/13898082

@tommy_trash can you answer me why you have used high-low>=10 in your code

what is wrong in my code https://www.codechef.com/viewsolution/13904747

They’ll be linked soon. I don’t have the power to put them by myself.

1 Like

This is the easiest solution for this problem.

1 Like

Yes, right, I was indexing from 0 by mistake. Thanks!

You need to take some small cases and plot the graph. That will surely help!

@sahil_g would you please tell why do minima occur at the median value of S[i]-i.L?

1 Like