C - Approximate Equalization 2 Editorial by en_translator
Suppose that the sequence \(A\) results in a sequence \(B\) by repeatedly perform the operation. Since the sum of the elements in the sequence is invariant by the operation, the sums of elements of \(A\) and \(B\) must be equal. We will now assume this property.
This problem is divided into the following two steps.
- Given a fixed \(B\), find the minimum number of operations required to make \(A\) equal \(B\).
- Among all \(B\) whose maximum and minimum values differ at most by one, find one that requires minimum number of operations, which is obtained by 1..
1. Given a fixed \(B\), find the minimum number of operations required to make \(A\) equal \(B\).
Let \(S\) be the sum of \(|A_k - B_k|\) over all \(k\ (1 \leq k \leq N)\). In an operation, decreasing \(A_i\) changes \(S\) by \(\pm 1\), and increasing \(A_j\) also changes \(S\) by \(\pm 1\); thus, an operation decreases \(S\) by at most two. Now, our objective is to make \(A\) equal \(B\), i.e. make \(S\) equal \(0\), so obviously at least \(\frac{S}{2}\) operations is required (we can prove that this value is an integer). Conversely, we can always make \(A\) equal \(B\) with \(\frac{S}{2}\) operations.
Proof
It is sufficient to show that "if $S > 0$, then there is an operation that decreases $S$ by $2$."
Since $S > 0$, at least one of "$i$ with $A_i > B_i$" and "$j$ with $A_j < B_j$" exists. Without loss of generality, assume that an $i$ with $A_i > B_i$ exists; then we can prove that a $j$ with $A_j < B_j$ also exists. This is because, if there is no such $j$, the sum of the elements of $A$ is greater than that of $B$, violating the assumption. Thus, taking arbitrary "$i$ with $A_i > B_i$" and "$j$ with $A_j < B_j$" to decrease $A_i$ by $1$ and increase $A_j$ by $1$, we can decrease $S$ by $2$. (Q.E.D.)
Therefore, the answer to this subproblem turns out to be \(\displaystyle \frac{\sum_{k = 1}^{N} |A_k - B_k|}{2} \). By the way, this is often used in many mid- and high-level problems, so the result may be worth remembering.
2. Among all \(B\) whose maximum and minimum values differ at most by one, find one that requires minimum number of operations, which is obtained by 1..
First of all, in order that
- the sum of elements of \(B\) equals that of \(A\); and
- the maximum and minimum values of \(B\) differ at most by one,
\(B\) must consist of \((N-r)\) copies of \(p\) and \(r\) copies of \((p+1)\), where \(p\) and \(r\) are respectively quotient and remainder when the sum of elements of \(A\) is divided by \(N\).
With the result in step 1., the problem is boiled down to the following problem.
- Among \(B\)s consisting of \((N-r)\) copies of \(p\) and \(r\) copies of \((p+1)\), find one that minimizes \(\displaystyle \sum_{k = 1}^{N} |A_k - B_k|\).
Intuitively, when \(i = 1,2,\dots,N\) are sorted in ascending order of \(A_i\), letting \(B_i =p\) for the first \((N-r)\) instances of \(i\) and \(B_i =p+1\) for the last \(r\) instances of \(i\) seems optimal. Indeed, this intuition is correct.
Proof
It is sufficient to prove that, if there are $i$ and $j$ such that $A_i < A_j$ and $B_i > B_j$, then swapping $B_i$ and $B_j$ does not increase $|A_i - B_i|+|A_j - B_j|$. This can be shown by simply dividing into cases by the ordering of $A_i,A_j,B_i$, and $B_j$ (which we omit the details).
Therefore, the problem has been solved in a total of \(O(N \log N)\) time, with sorting \(A\) being the bottleneck. See also the sample code below. One can also solve it in an \(O(N)\) time with, for example, std::nth_element
.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<int> a(n);
ll sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
sort(a.begin(), a.end());
vector<int> b(n, sum / n);
for (int i = 0; i < sum % n; i++) {
b[n - 1 - i]++;
}
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(a[i] - b[i]);
}
cout << ans / 2 << endl;
}
Sample code (Python) :
n = int(input())
a = list(map(int, input().split()))
sum = sum(a)
a.sort()
b = [sum // n for i in range(0, n)]
for i in range(0, sum % n):
b[n - 1 - i] += 1
ans = 0
for i in range(0, n):
ans += abs(a[i] - b[i])
print(ans // 2)
posted:
last update: