CONSESNK - Editorial

editorial
, , , , ,
6

“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

7

Is there any simple O(n) solution

Thanks in advance

8

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?

9

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.

10

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

11

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

12

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

13

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

14

why am I getting TLE? CodeChef: Practical coding for everyone

15

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

what is wrong in my code CodeChef: Practical coding for everyone

16

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

1 Like
17

This is the easiest solution for this problem.

1 Like
18

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

19

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

20

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

1 Like
21

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.

22

this is my solution . CONSESNK - Unofficial Editorial - general - CodeChef Discuss Hopefully this is what you are looking for

23

Due to sorting my solution is O(nlogn) . However my solution is simpler.
https://discuss.codechef.com/questions/99473/consesnk-unofficial-editorial

24

Due to sorting my solution is O(nlogn) . However my solution is simpler.
https://discuss.codechef.com/questions/99473/consesnk-unofficial-editorial

25

CONSESNK - Unofficial Editorial - general - CodeChef Discuss …
Maybe this is what you are looking for .