Invariant Ball Difference
Autumn Tournament (2015)
Submission name: balls.cpp
Problem summary
Encode red balls by positive counts and blue balls by negative counts. In each simultaneous step, compute the current signed sum S and replace every a[i] by S−a[i]. After K steps, find the difference between the largest and smallest encoded counts.
Source clarification. The story discusses physical ball counts, but the official analysis explicitly computes max(a)−min(a) for the signed array. This solution follows that intended mathematical interpretation. Editorial: https://infos.infosbg.com/files/Contests/ETI/2015/D/analyses/balls_analysis.pdf
Input
N and K, then N signed integer counts.
Output
The final maximum minus the final minimum.
Constraints
2 ≤ N ≤ 1000000; 1 ≤ K ≤ 1000; −2000000000 ≤ a[i] ≤ 2000000000.
Worked example
Original statement sample.
Input
3 2 -7 1 -3
Output
8
Solution analysis
- Simulating K steps is unnecessary and may create enormous intermediate numbers. For a fixed step, subtracting from the same sum reverses order: the old minimum becomes the new maximum, and the old maximum becomes the new minimum.
- Consequently newMaximum=S−oldMinimum and newMinimum=S−oldMaximum. Their difference is oldMaximum−oldMinimum: the sum cancels. The range is invariant under every step, so scan the input once and ignore K after reading it.
- For −7,1,−3 the initial range is 1−(−7)=8. The first transformed values are −2,−10,−6, still of range 8; the next are −16,−8,−12, again of range 8. Only the initial extrema are needed.
Why it works
For any two values, a[i]≤a[j] implies S−a[i]≥S−a[j]. Thus the stated formulas for the new extrema hold, and subtracting them preserves the range. Induction over K proves that the initial maximum minus minimum is the requested final result.
Watch out. Updates are simultaneous, not sequential. Do not simulate values that can overflow. The official editorial treats maximum/minimum as signed encoded values; replacing every value by its absolute magnitude is a different problem.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int count;
int steps;
cin>>count>>steps;
long long value;
cin>>value;
long long minimum=value;
long long maximum=value;
for(int index=1;index<count;++index){
cin>>value;
minimum=min(minimum,value);
maximum=max(maximum,value);
}
// The signed range is invariant, regardless of the number of steps.
cout<<maximum-minimum<<'\n';
}