UVa 11300

Posted on | In ,

Spreading the Wealth

Solution sketch

For every position $i$, we can define a variable $x_i$ which stores the number of coins that are being transferred from position $i + 1$ to $i$.

Let’s define the number of coins of each person as $a_1$, $a_2$, …, $a_n$, and the final state as $avg = \frac{sum\ of\ coins}{n}$.

We know that $a_1$ must end up being $avg$, by subtracting the coins he transferred to his left, and adding the coins transferred to him from the right. Thus, we can get
$$a_1 - x_1 + x_2 = avg$$
Rewrite the equation
$$
\begin{equation}
x_2 = x_1 - (a_1 - avg)
\end{equation}
$$

We also know that $a_2$ must end up being $avg$, so we can get
$$a_2 - x_2 + x_3 = avg$$
Rewrite the equation
$$
\begin{equation}
x_3 = x_2 - (a_2 - avg)
\end{equation}
$$
Substitute $x_2$ in equation 2 by using equation 1, we can get
$$x_3 = x_1 - [(a_1 + a_2) - 2 \times avg]$$

Continue on doing this operation for all remaining $a_k$, you will get the pattern like
$$\begin{aligned} x_k = x_1 - [ ( a_1 + a_2 + ... + a_{k - 1} ) - (k - 1) \times avg] \end{aligned}$$

One thing to notice is that the equation for $a_n$ is a special case, you can think about it :)

Since we are solving for the smallest $|x_1| + |x_2| + |x_3| + … + |x_n|$, we can substitute all $x_k$ with the equations solved above and get something like $|x_1| + |x_1 - (a_1 - avg)| + |x_1 - [(a_1 + a_2) - 2 \times avg]| + …$. Observe that if we use median for $x_1$, we can get the minimal sum.

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        ll prefix[n], sum = 0;
        for (int i = 0; i < n; i++) {
            ll cur;
            scanf("%lld", &cur);
            sum += cur;
            if (i == n - 1)
                break;
            prefix[i] = (i == 0 ? cur : prefix[i - 1] + cur);
        }
        ll avg = sum / n;
        for (int i = 0; i < n - 1; i++)
            prefix[i] -= (i + 1) * avg;
        sort(prefix, prefix + n - 1);
        ll mid = prefix[(n - 1) / 2];
        ll res = llabs(mid);
        for (int i = 0; i < n - 1; i++)
            res += llabs(mid - prefix[i]);
        printf("%lld\n", res);
    }
    return 0;
}