# Internet Problem Solving Contest

## Solution to Problem B – Load Balancing

Clearly it is possible to rebalance the jobs if and only if total number of jobs currently assigned to processors is divisible by number of processors N. Now let's suppose that it is (otherwise the solution is -1). Let d denote the number of jobs to be assigned to each processor after rebalancing and Pi denote the number of jobs currently assigned to processor i.

Let's compute for each processor i the values ri and li denoting number of jobs to be transferred to left and right neighbour of i-th processor respectively. Clearly the solution will be the maximum of values ri and li over all 1<=i<=N. Let's consider the first processor. If the number of jobs currently assigned to this processor is less than d this processor must receive d-P1 jobs from processor 2. No other jobs need to be transferred from 2 to 1(solution transferring more jobs from 2 to 1 cannot be better). So l1=r1=0 and l2=d-P1. If P1>d then similarly l1=0,r1=P1-d,l2=0. We can compute the values ri and li+1 for other i in similar way. If Vi=Pi-li+ri-1<d then ri=0 and li+1=d-Vi, if Vi>d then ri=Vi-d and li+1=0.