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
Due to sorting my solution is O(nlogn) . However my solution is simpler.
https://discuss.codechef.com/questions/99473/consesnk-unofficial-editorial
Due to sorting my solution is O(nlogn) . However my solution is simpler.
https://discuss.codechef.com/questions/99473/consesnk-unofficial-editorial
CONSESNK - Unofficial Editorial - general - CodeChef Discuss …
Maybe 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.
@prak_blah this answer on math.stackexchange will help you understand the intuition- optimization - The median minimizes the sum of absolute deviations (the $ {\ell}_{1} $ norm) - Mathematics Stack Exchange
1 Like