SPOJ.com - Problem BALIFE

BALIFE - Load Balancing

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.

Example

Input file:
3
0 99 3

2
49 50

8
16 17 15 0 20 1 1 2

10
0 0 100 0 0 0 0 0 0 0

-1

Output file:
34
-1
23
70

Submit solution!

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

hide comments

2021-04-28 13:35:57
do we have to transfer the job from a processor in order manner (means from left to right --> 1, 2, 3, 4.....N) or for each round we can chose any arbitrary processor exectly 1 time and transfer to the neighbour.(means 9,3,7,5,1,3.....N-K, ... )

Last edit: 2021-04-28 13:58:49

2020-08-22 19:48:58
AC in one go

2020-03-31 20:34:40
O(n) and AC in one go!
0.00 sec && 4.4M

2019-10-12 17:34:22
AC in one go.

2019-08-31 10:06:36
process of input data in python:
N jobs can be separated by spaces and/or end of line characters so,

1. maintain a list of jobs, initially empty
2. take input, split in numbers and add in jobs
3. repeat step 2 untill len(jobs) not equal to n
4. don't forget the blank line after step3

2019-06-04 07:22:13
refer to this link if you want to understand the logic
https://www.quora.com/What-is-the-approach-to-solve-SPOJ-com-Problem-BALIFE

2019-04-16 09:18:40
@devil_3 try solving it with pen and paper. You'll get it.

2019-01-10 08:56:37
Can you guys tell me how you come up with the approach of prefix sum array? Actually how you realized that we should use this or by just hit and trial

2018-08-12 05:45:29
Very easy to get AC in one go! Few hints:

1. Make prefix sum of main and prefix sum of average array.
2. Take the maximum absolute difference between them, that is the answer.
3. Check if the average is divisible by n, if not then it can obviously not be rebalanced.
4. Take special care of the -1 at the end of the input.
5. Constraints are, n <= 111111.

Happy coding :)

Last edit: 2018-08-12 05:47:19

2018-06-22 13:59:42
Prefix Sum of initial array and balanced array :)