USACO OPEN07 Problem 'horizon' Analysis
by Richard Ho
Suppose you take the x-coordinates of where each building starts (A_i) and ends
(B_i) and sort these 2N numbers. This divides the horizon into (at most) 2N-1
pieces, call them x_1, x_2, x_3, ..., x_k. We know then that the maximum height
of the aggregate silhouette is constant in each of the intervals [x_1,x_2],
[x_2,x_3], ..., [x_(k-1),x_k]. In fact, if we knew the maximum heights h_1,
h_2, ... h_(k-1) for each of the intervals, then the total area is just
(x_2-x_1)*h_1 + (x_3-x_2)*h_1 + ... + (x_k-x_(k-1))*h_(k-1). So let us try to
find these maximum heights instead.
One way to do this is, for each interval, we go through all the buildings and
see which ones contain that interval, and take the tallest of those. However,
this is very slow, since for each of the 2N-1 intervals, we would have to go
through N buildings, giving us something with a runtime of O(N^2). With N up to
40,000, this is going to be too slow.
Instead we can sweep from left to right and add a height to a list (allowing
repetitions) when a building starts, and remove that height from the list when
a building ends. The highest number in the list represents the height of the
silhouette at that point. So we can just sort the building's start and end
locations (making sure to store whether its a start or end, and the associated
height). We sweep from left to right, and process all the heights at the same
coordinate (buildings can start or end where another building starts or ends)
and remember what the final heights were for each coordinate. We know that the
height at position x_i is the height of the silhouette on the interval [x_i,
x_(i+1)]. Now, if we just used a simple list, each height we process can take
up to O(N). But if we used a max-heap (i.e. binary tree where parents are
always larger than both children), then each height we process can take up to
O(log N), since heap insertions and removals are logarithmic. This would give
us a final runtime of O(N log N), which is sufficient.
However, if you really do not like coding data structures from scratch (due to
bugs or just plain boredom), then it is worth the effort to learn to use your
languages libraries for data
structures. Below is a (short) solution from Christos Tzamos that uses STL's
map and multiset, which are already sorted containers!
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
map<int,vector<pair<int,int> > > M;
map<int,vector<pair<int,int> > >::iterator it;
vector<pair<int,int> >::iterator i;
multiset<int, greater<int> > S;
int main() {
int N,L,a,b,h,opens,k;
long long s=0;
freopen("horizon.in","r",stdin);
freopen("horizon.out","w",stdout);
scanf("%d",&N);
while(N--) {
scanf("%d %d %d",&a,&b,&h);
M[a].push_back(make_pair(h,1));
M[b].push_back(make_pair(h,0));
}
a = 0;
for(it=M.begin();it!=M.end();it++) {
b = it->first;
if(!S.empty()) s += (long long)(b - a)*(*S.begin());
a = b;
for(i=(it->second).begin();i!=(it->second).end();i++) {
k= i->first;
opens = i->second;
if(opens) S.insert(k);
else S.erase(S.find(k));
}
}
printf("%lld\n",s);
return 0;
}