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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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.
Name |
---|
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.
Thanks for the explanation :)
Can anybody prove the median thing if B[i] = 1?
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)
How can you assume the slope changes from -n to n? A[i] values can be anything
Ok thanks