### Sword_Of_The_Morning's blog

By Sword_Of_The_Morning, history, 7 weeks ago, ,

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

 » 7 weeks ago, # |   +7 sort the array A and adjust B accordingly. x can only take values of A[i]. Now have prefix sum and suffix sum's of B[i] and A[i]*B[i]. Iterate x over A[i] and calculate the minimum of the expression
 » 7 weeks ago, # | ← 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.
•  » » 7 weeks ago, # ^ |   0 Thanks for the explanation :)
 » 5 weeks ago, # |   +1 Can anybody prove the median thing if B[i] = 1?
•  » » 5 weeks ago, # ^ |   +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 weeks ago, # ^ |   +1 How can you assume the slope changes from -n to n? A[i] values can be anything
 » 5 weeks ago, # |   0 Ok thanks