Shuaib's blog

By Shuaib, 7 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

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

    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.

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

    Thanks for this excellent explanation. :)

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

      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].

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

    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.

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

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

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