CONSESNK - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: admin3
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak

DIFFICULTY:

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.

2

Not able to see the solutions. It says Access denied.

3

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
4

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

1 Like
5

Any simple o(n) solution…

6

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

7

“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

8

Is there any simple O(n) solution

Thanks in advance

9

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?

10

This is the easiest solution for this problem.

1 Like
11

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

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.

12

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

13

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

14

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

15

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

16

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

1 Like
17

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

18

You can do that also in O(N) in the worst case, but there is no point for such optimizations :slight_smile: Notice that initial sorting phase of the segments has O(N * log(N)) complexity.

19

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…

link text

20

this is my solution . https://discuss.codechef.com/questions/99473/consesnk-unofficial-editorial Hopefully this is what you are looking for