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

Автор Shuaib, 11 лет назад, По-английски

So CR 177 (DIV2) had a general case of the problem where you have to make all the elements in a sequence same, using minimum number of steps. Where each step is incrementing or decrementing an element by constant integer d.

Can anyone shed some light on this problem. How to approach such a problem.

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

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

One can prove that the minimum number of steps is given when every number sum up to the median of all elements.

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

If the numbers aren't all equal modulo d, then it's impossible because no matter what you do, their moduli by d are invariant. Otherwise, the number of steps won't change if you have the same sequence, but subtract each element's remainder modulo d from it, so all the elements are divisible by d. And now, just imagine that you divided every element by d; the number of steps for the original sequence with d is the same as for this new sequence with d=1. So the problem simplifies to d=1.

Now to d=1. It's similar to what MDantas said, but more precisely: if the number of elements is odd, then you want to get all the numbers to their median, and if it's even, then there's no single median — there's the (n/2)th and (n/2+1)st number in the sorted order, and the number of steps is the same if you get all the numbers to any value between those two, inclusive.

Now to the proof. If the numbers are equal, you don't need to do anything. Otherwise, imagine you want to get all the numbers a[i] to x, and that there's such an i that a[i] < x <= a[i+1] (it's obvious that if x <= a[1] or x > a[n], then there's a better solution obtained by increasing resp. decreasing x). Then the number of steps is sum(j=1..n): |a[j]-x| = sum(j=i+1..n): (a[j]-x) + sum(j=1..i): (x-a[j]) By decreasing x, i numbers move closer to x and n-i numbers further from it, so the answer increases by n-2i. If the solution is optimal, then this step can't decrease the answer, so n >= 2i. By an analogous process with increasing x with a[i] <= x < a[i+1], we get n <= 2i. That leads to the median for sequences of odd length and the 2 next-to-medians for those of even length.

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

    Yes, that's the complete answer. To avoid some tricky cases in problems like that, I usually test every number on the range between the (n/2 — X)th and the (n/2 + X)th element. It isn't necessary but avoids all possible corner cases.

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

    Thanks for this excellent explanation. :)

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

    can you please xplain this thing to me ?

    Then the number of steps is sum(j=1..n): |a[j]-x| = sum(j=i+1..n): (a[j]-x) + sum(j=1..i): (x-a[j]) By decreasing x, i numbers move closer to x and n-i numbers further from it, so the answer increases by n-2i. If the solution is optimal, then this step can't decrease the answer, so n >= 2i. By an analogous process with increasing x, we get n <= 2y where a[y] <= y < a[y+1].

    I am confused with the notation you have used. thanks.

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

      Yeah, the last sentence is a mess (but the rest is correct). Edited.