Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

nmnsharma007's blog

By nmnsharma007, 8 days ago, In English,

Hello Codeforces,

I was trying to solve SPOJ BALIFE question. As I couldn't make sense of the question much and the test cases, I read the comments and also tried Google to find some explanation. But all I came to know was that this question is solved using prefix-sum technique. Can someone please explain how this question uses that approach and also the step by step explanation of how the the test cases are working? More specifically, maybe someone can explain using the below sample test case given in the question itself:

8

16 17 15 0 20 1 1 2

I would appreciate your help.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Define fromRight[i] = number of jobs processor i got from processor i + 1. We can let fromRight[i] be negative if processor i gives jobs to processor i + 1. Clearly fromRight[0] = goal - A[0], where goal is the average of the input array A. Also we know we must subtract fromRight[0] from A[1] now because we know for certain that this change must happen in the process of reaching balance, regardless of how it is reached. Then for i (1 <= i < N) we can do the same thing:

fromRight[i] = goal - A[i];
A[i + 1] -= fromRight[i];

Then the answer is at least the max value of abs(fromRight[i]) (0 <= i < N). It turns out this is actually answer, but I'm unable to give a proof other than proof by AC.