Contest Duration: - (local time) (100 minutes) Back to Home
Official

## G - Approximate Equalization Editorial by en_translator

First of all, consider the minimum number of operations required to make an integer sequence $$A=(A_1,A_2,\ldots,A_N)$$ equal another given sequence $$B=(B_1,B_2,\ldots,B_N)$$.

Firstly, if the sums are different, i.e. if $$\displaystyle\sum_{i=1}^N A_i \neq \sum_{i=1}^N B_i$$, then you cannot make $$A$$ equal $$B$$, because the operation in the problem statement does not change the sum.
On the other hand, if the sums are equal, one can always make $$A$$ equal $$B$$ with $$\left( \displaystyle\sum_{i=1}^{N-1}\lvert S_i-T_i\rvert \right)$$ operations, where $$S_i=\displaystyle\sum_{k=1}^i X_k$$ and $$T_i=\displaystyle\sum_{k=1}^i Y_k$$ for all $$0\leq i\leq N$$. This is because the operation in the problem statement effectively modifies $$S_i$$ as follows:

• choose an integer $$i$$ such that $$1\leq i\leq N-1$$ to decrease $$S_i$$;
• choose an integer $$i$$ such that $$1\leq i\leq N-1$$ to increase $$S_i$$,

and there are one-by-one correspondences between “$$(S_0=0,S_1,S_2,\ldots,S_{N-1},S_N)$$ and $$(A_1,A_2,\ldots,A_N)$$” and “$$(T_0=0,T_1,T_2,\ldots,T_{N-1},T_N)$$ and $$(B_1,B_2,\ldots,B_N)$$”. (Note that $$S_N=T_N$$ naturally holds because they have the same sum.)

Next, consider the candidates of the final conforming $$B=(B_1,B_2,\ldots,B_N)$$ from the given $$A$$. First, by the conditions in the problem statement, there must exist an integer $$x$$ such that each $$B_i$$ is either $$x$$ or $$x+1$$. Moreover, by the condition of the sequence that can be obtained from $$A$$ by the operation, $$\displaystyle\sum_{i=1}^N B_i=S_N$$ should hold.

Then, if $$B_i\leq \frac{S_N}{N}-1$$ for some $$i$$, then $$\displaystyle\sum_{i=1}^N B_i\leq (\frac{S_N}{N}-1)+(N-1)\times\frac{S_N}{N}=S_N-1$$, so it is inappropriate. Similarly, if $$B_i\geq \frac{S_N}{N}+1$$ for some $$i$$, then $$\displaystyle\sum_{i=1}^N B_i\geq (\frac{S_N}{N}+1)+(N-1)\times\frac{S_N}{N}=S_N+1$$, so it is also inappropriate. Therefore, each $$B_i$$ should be an integer such that $$\frac{S_N}{N}-1<B_i<\frac{S_N}{N}+1$$.

• If $$S_N$$ is not a multiple of $$N$$

$$B_i=\lfloor \frac{S_N}{N}\rfloor$$ or $$\lfloor\frac{S_N}{N}\rfloor+1$$ should hold for all $$i$$ (where $$\lfloor\frac{S_N}{N}\rfloor$$ denotes the maximum integer no greater than $$\lfloor\frac{S_N}{N}\rfloor$$). Among integers $$i$$ such that $$1\leq i\leq N$$, if $$k$$ integers of them satisfy $$B_i=\lfloor\frac{S_N}{N}\rfloor+1$$ and $$(N-k)$$ of them satisfy $$B_i=\lfloor\frac{S_N}{N}\rfloor$$, then $$S_N=\displaystyle\sum_{i=1}^NB_i=N\cdot\left\lfloor\frac{S_N}{N}\right\rfloor+k\equiv k\pmod{N}$$. Thus, if we represent $$S_N=N\cdot \lfloor\frac{S_N}{N}\rfloor+r$$ ($$1\leq r\leq N-1)$$, then $$B$$ must be composed of $$r$$ copies of $$\lfloor\frac{S_N}{N}\rfloor+1$$ and $$(N-r)$$ copies of $$\lfloor\frac{S_N}{N}\rfloor$$. Conversely, if it is composed of them, then the condition in the problem statement is satisfied, and also $$A$$ can be changed into $$B$$.

• If $$S_N$$ is a multiple of $$N$$

$$B_i=\frac{S_N}{N}$$ must hold for all $$i$$, and it indeed satisfies the condition. This can be considered as the $$r=0$$ case of the non-multiple-of-$$N$$ $$S_N$$ above.

The minimum value of $$\displaystyle\sum_{i=1}^{N-1}\lvert S_i-T_i\rvert$$ over all candidates of $$B$$ can be found with a Dynamic Programming (DP).

Let $$dp[i][j]$$ $$(0\leq i\leq N, 0\leq j\leq \min(i,r))$$ be the minimum value of $$\displaystyle\sum_{k=1}^{i}\lvert S_k-T_k\rvert$$ such that, among $$B_1,B_2,\ldots$$, and $$B_i$$, $$j$$ elements $$B_k$$ satisfy $$B_k=\lfloor\frac{S_N}{N}\rfloor+1$$; then $$dp[0][0]=0$$ and

$dp[i][j]=\min(dp[i-1][j-1],dp[i-1][j])+\left\lvert i\cdot\left\lfloor\frac{S_N}{N}\right\rfloor +j-S_i\right \rvert.$

(Here, $$dp[i-1][j-1]=+\infty$$ if $$j=0$$ and $$dp[i-1][j]=+\infty$$ if $$j=i$$.) The answer is the value $$dp[N][r]$$. Since each $$dp[i][j]$$ can be found from $$dp[i-1][j-1]$$ and $$dp[i-1][j]$$ in an $$O(1)$$ time, the overall complexity is $$O(N^2)$$; since the constraints guarantee that $$N\leq 5000$$, the answer can be found fast enough.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void){
int n,r;
long long d;
long long a[5000],dp[5000],dp2[5000];

cin>>n;
for(int i=0;i<n;i++)cin>>a[i];

for(int i=0;i<n-1;i++)a[i+1]+=a[i];
if(a[n-1]>=0){
d=a[n-1]/n;
r=a[n-1]%n;
}
else{
r=(n-(-a[n-1])%n)%n;
d=(a[n-1]-r)/n;
}

dp[0]=0;
for(int i=0;i<n;i++){
dp2[0]=dp[0]+abs(d*(i+1)-a[i]);
for(int j=0;j<min(r,i);j++)dp2[j+1]=min(dp[j],dp[j+1])+abs(d*(i+1)+j+1-a[i]);
if(i+1<=r)dp2[i+1]=dp[i]+abs((d+1)*(i+1)-a[i]);
for(int j=0;j<=min(r,i+1);j++)dp[j]=dp2[j];
}

cout<<dp[r]<<endl;
return 0;
}


posted:
last update: