Proficient.
Put your skills to the test.

Problem summary

N processors form a line. In one simultaneous step each processor may send one job to either neighbor, one to each neighbor, or none. Find the minimum steps to equalize all job counts, or report impossibility.

Constraints

1 ≤ N ≤ 10000; each initial count is between 0 and 10000.

Worked example

An independently prepared example for this explanation.

3
0 99 3

34

Solution analysis

1. The total number of jobs must be divisible by N. Let average be the required final load and prefix[i] be the total excess in processors 1 through i relative to that average.
2. The edge between i and i+1 must carry exactly prefix[i] jobs net to the right, or its absolute value to the left. Each direction can carry at most one job per step, so the answer is at least the maximum absolute prefix excess. This bound is achievable by continuously forwarding along the required directions.
3. For loads 0,99,3 the average is 34. The first prefix needs 34 jobs from the right, and the second has 31 jobs to send right. The middle processor can send simultaneously to both sides, so 34 steps suffice.

Why it works

Every prefix must lose its exact excess across its only boundary edge, proving the lower bound. Direct each edge according to that excess and use it until its required flow is exhausted. A processor with two outgoing edges has surplus equal to the sum of their required flows, so it can sustain both. With one incoming and one outgoing edge, initial load minus final load equals outgoing flow minus incoming flow; because the final average is at least one unless all loads are zero, an initially empty processor can wait for the first incoming job without extending the maximum edge-flow bound. Equivalently, along any directed chain each initially empty transit introduces one delay while the required flow grows by at least one there. Thus all flows finish within the maximum absolute prefix excess.

Watch out. A processor may send to both neighbors in the same step. Do not use the formula for the variant allowing only one outgoing job total.

An independently written complete program with standard headers.

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    // Compute the exact archive answer using the method explained above.
    int n;
    cin>>n;
    vector<long long>load(n);
    long long total=0;
    for(long long&value:load){
        cin>>value;
        total+=value;
    }
    if(total%n!=0){
        cout<<-1<<'\n';
        return 0;
    }
    long long average=total/n;
    long long excess=0;
    long long answer=0;
    for(long long value:load){
        excess+=value-average;
        answer=max(answer,llabs(excess));
    }
    cout<<answer<<'\n';
}