Online Medians
National Olympiad — National round (2011 season)
Submission name: medians.cpp
Problem summary
Process additions of real numbers and requests for the median of all numbers added so far. For even size, average the two central sorted values.
Source clarification. The statement does not define the result of G on an empty sequence. Such requests are assumed absent; no invented numeric answer is printed for them.
Input
N, followed by N operations: A value or G.
Output
For each G, print the median with exactly three decimal places.
Constraints
1 ≤ N ≤ 200000; at most 100000 additions; added values lie in [−1000000, 1000000] and have at most two decimal places.
Worked example
An independently prepared example for this explanation.
Input
7 A 5 A 7 A -4 A 8.00 G A 10 G
Output
6.000 7.000
Solution analysis
- Keep the lower half in a maximum heap and the upper half in a minimum heap. Every lower value must be at most every upper value, and the lower heap has either the same size as the upper heap or one extra element.
- Insert into the appropriate half and move a heap top if necessary to restore the size invariant. The median is the lower top for odd size, or the average of both tops for even size. Because the input has at most two decimals, every possible median is exactly representable with three decimal digits mathematically.
- After adding 5, 7, −4 and 8, the halves can be {−4,5} and {7,8}; their central values give 6.000. Adding 10 makes the sorted middle value 7, giving 7.000.
Why it works
Insertion preserves the order between halves, and moving their boundary value restores their balanced sizes without breaking that order. Thus their tops are exactly the required middle element or middle pair.
Watch out. Rebalance after every addition. Average after converting to a real type. A median of an empty sequence is undefined; the solution assumes G is requested only after an addition.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<iomanip>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int operations;
cin>>operations;
priority_queue<double>lower;
priority_queue<double,vector<double>,greater<double>>upper;
cout<<fixed<<setprecision(3);
while(operations--){
char type;
cin>>type;
if(type=='A'){
double value;
cin>>value;
if(lower.empty()||value<=lower.top()){
lower.push(value);
}
else{
upper.push(value);
}
// Keep the lower half at most one element larger.
if(lower.size()>upper.size()+1){
upper.push(lower.top());
lower.pop();
}
if(upper.size()>lower.size()){
lower.push(upper.top());
upper.pop();
}
}
else if(!lower.empty()){
double median=lower.top();
if(lower.size()==upper.size()){
median=(median+upper.top())/2.0;
}
if(median==0.0){
median=0.0;
}
cout<<median<<'\n';
}
}
}