BALIFE - Load Balancing

no tags 

SuperComputer Inc. have built a super-fast computer server consisting of N hyper-scalar lightning-fast processors Beta 007. These processors are numbered from 1 to N and are used to process independent jobs. Every new incoming job is assigned to an arbitrary processor. Sometimes, a processor may be assigned too many jobs while other processors have a relatively light load (or even wait idly). In that case, the whole system undergoes rebalancing.

Rebalancing proceeds in rounds. In each round, every processor can transfer at most one job to each of its neighbors on the bus. Neighbors of the processor i are the processors i-1 and i+1 (processors 1 and N have only one neighbor each, 2 and N-1 respectively). The goal of rebalancing is to achieve that all processors have the same number of jobs.

Given the number of jobs initially assigned to each processor, you are asked to determine the minimal number of rounds needed to achieve the state when every processor has the same number of jobs, or to determine that such rebalancing is not possible.

Input file specification

The input file consists of several blocks. Each block begins with a line containing a single number N(1<= N <=9000) - the number of processors. N numbers follow, separated by spaces and/or end of line characters. The i-th number denotes the number of jobs assigned to the i-th processor before rebalancing. There is a blank line after each block. The last block is followed by a single number -1 on a separate line (which should not be processed).

Output file specification

For each block in the input file, output the minimal number of rounds needed to rebalance loads for all the processors. If it is not possible to rebalance jobs so that each processor has the same number of jobs, output -1.


Input file:
0 99 3

49 50

16 17 15 0 20 1 1 2

0 0 100 0 0 0 0 0 0 0


Output file:

hide comments
doluongk56: 2016-12-05 05:39:12

O(n) - AC in one go.

detel: 2015-07-18 23:29:57

Try not to use string reading input for languages like Python/Java as there's an extra EOF at the end of number of jobs!!!

Brian Bi: 2014-05-03 06:40:07

In case it's not clear, a processor in the middle doesn't have to transfer one job to each neighbour. It can choose in each round not to transfer, to transfer to only one neighbour, or to transfer to both neighbours.

Brian Bi: 2014-05-02 23:02:03

Problem description should specify bounds on # of jobs initially assigned to each processor. (Looking at original test data from IPSC, it seems the maximum value is 10153)

SanchitK: 2013-12-03 09:17:03

my codes works well for the given test cases but spoj gives WA.
please give more test cases.

aar: 2013-10-17 07:51:27

Test Case: 6 0 0 10

张翼德: 2012-12-13 12:34:28

lame ques costed me 7 NZEC's in C#

P.S. - there's an extra end of line at the end of no. of jobs... take care of it.

Last edit: 2012-12-13 12:43:02
tranquil: 2012-11-07 15:53:48

any hints??

Artur Tadra³a: 2012-01-18 13:43:26

Note that input contains end of line between number of jobs. I missed that.

Added by:Fudan University Problem Setters
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:IPSC 2002