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

MInimize SUM(|x — A[i]|*B[i]), i >= 0 and i < N, B[i] > 0
Автор Aafat_Wapas, история, 5 лет назад, По-английски

How To Find the minimum value of the expression below:

SUM(|x - A[i]|*B[i]), i >= 0 and i < N, B[i] > 0

When B[i] = 1 I know the answer is given by x = Median(A).How to calculate x when B itself varies.

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

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
  1. sort the array A and adjust B accordingly.
  2. x can only take values of A[i].
  3. Now have prefix sum and suffix sum's of B[i] and A[i]*B[i].
  4. Iterate x over A[i] and calculate the minimum of the expression
→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

Another way to think about this is to imagine you have a new array $$$A'$$$ such that it has element $$$A_i$$$ repeated $$$B_i$$$ times in it. Now it is easy to see that the answer to your problem for $$$A'$$$ and $$$B'_i = 1$$$ will be the same as the one for $$$(A, B)$$$. This means that we can simply find the median of $$$A'$$$.

To do this fast, we sort the pairs $$$(A_i, B_i)$$$ by $$$A$$$, then we find the sum of all $$$B_i$$$ and go from the beginning while the prefix sum of $$$2 * B_i < SumB$$$. The last $$$A$$$ we have went through will be our answer.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can anybody prove the median thing if B[i] = 1?

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    The function $$$f(x) = \sum_{i = 1}^{n} |x - a_i| $$$ is a piecwise linear function, meaning that it can be broken into straight lines, and changes slope at breakpoints $$$a_i$$$'s, which confirms that minimum is achieved at one of $$$a_i$$$'s. Now as you move from $$$-\infty$$$ to $$$+\infty$$$ slope changes from $$$-n$$$ to $$$n$$$, and is $$$0$$$ at median (when exactly half terms contribute +1 to slope and other half -1)

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

Ok thanks

→ Ответить