Hello everyone, Can anyone just confirm how the graph of cost and the final height (same for all) would look like in this question? What I think is it would be unimodal function (having exactly one minima) but i don't know if it is correct. please tell me so i can edit. i just wanted to know just how graph of total cost for modifying all sticks to some particular same height would look like w.r.t to that height. please please help me https://cses.fi/problemset/task/1074

Lets take an example of 3 sticks only:

$$$cost(x) = |x-x_0| + |x-x_1| + |x-x_2| $$$

Lets try to visualise how our cost function will change when x goes from $$$(-\infty, +\infty)$$$

$$$>$$$ denotes increasing

$$$<$$$ denotes decreasing

(number of increasing functions) $$$>=$$$ (number of inc functions in previous interval)

thanks a lot so just to confirm i can use ternary search to calculate that final height for minimum cost right? i know there is a simple approach as well but i just thought to implement ternary search in a problem.

you can just take the median of the array to be your final height as the median minimizes the sum of absolute difference.

Yes, I solved it using ternary search

Can you please share the solution? it would be really helpful

Ternary search approach