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.
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…
link text
@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
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
You can do that also in O(N) in the worst case, but there is no point for such optimizations Notice that initial sorting phase of the segments has O(N * log(N)) complexity.
this is my solution . CONSESNK - Unofficial Editorial - general - CodeChef Discuss Hopefully this is what you are looking for
@sanyamg123 I still cant figure out how f(x)=∑1≤i≤N|x+(i−1)⋅L−Si| this function is generated. Can you please explain it in detail?
Do not use the data type as double. Use integer or long long int. And use the formulas for calculating m1 and m2 as : m1=low+(high-low)/3; m2=high-(high-low)/3; This will give you an AC.