Virtual_Contestant's blog

CSES: Will the graph be unimodal?
By Virtual_Contestant, history, 4 years ago, In English

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

Range $$$x$$$ $$$|x-x_0|$$$ $$$|x-x_1|$$$ $$$|x-x_2|$$$
$$$(-\infty, x_0)$$$ $$$<$$$ $$$<$$$ $$$<$$$
$$$(x_0, x_1)$$$ $$$>$$$ $$$<$$$ $$$<$$$
$$$(x_1, x_2)$$$ $$$>$$$ $$$>$$$ $$$<$$$
$$$(x_2, \infty)$$$ $$$>$$$ $$$>$$$ $$$>$$$
  • We see that in every interval,
    (number of increasing functions) $$$>=$$$ (number of inc functions in previous interval)
  • Also, rate of increase for each function is also same (unit for every unit change of x)
  • So the overall cost function decreases till count of decreasing functions > count of increasing functions, eventually hits a minima when counts become equal and then starts increasing again. Hence, $$$unimodal$$$.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I solved it using ternary search

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Ternary search approach
          → Reply