Internet Problem Solving Contest

• Correct output – B1
• Correct output – B2
• C program solving both data sets

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₁ 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₁=r₁=0 and l₂=d-P₁. If P₁>d then similarly l₁=0,r₁=P₁-d,l₂=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.