## IPSC 2002

## 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 **P**_{i} denote the number of jobs currently
assigned to processor **i**.

Let's compute for each processor **i** the values **r**_{i} and
**l**_{i} 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 **r**_{i} and **l**_{i} 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-P**_{1} 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 **l**_{1}=r_{1}=0
and **l**_{2}=d-P_{1}. If **P**_{1}>d then
similarly **l**_{1}=0,**r**_{1}=P_{1}-d,**l**_{2}=0.
We can compute the values **r**_{i} and **l**_{i+1} for other **i**
in similar way. If **V**_{i}=P_{i}-l_{i}+r_{i-1}<d
then **r**_{i}=0 and **l**_{i+1}=d-V_{i}, if
**V**_{i}>d then **r**_{i}=V_{i}-d and **l**_{i+1}=0.