CONSESNK - Editorial

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.

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 .

CONSESNK - Unofficial Editorial - general - CodeChef Discuss .
Check out my unofficial editorial.

@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