Блог пользователя Virtual_Contestant

Автор Virtual_Contestant, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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$$$.
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, I solved it using ternary search

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ternary search approach