Mountain Lakes
National Olympiad — National round (2011 season)
Submission name: ezera.cpp
Problem summary
A mountain profile consists of /, \ and _, each spanning one horizontal unit. After all bounded valleys fill and overflow, count the separate lakes and their total cross-sectional area; one unit of area represents one cubic metre.
Input
One profile string.
Output
The number of lakes and their combined volume.
Constraints
Profile length at most 10000.
Worked example
An independently prepared example for this explanation.
Input
//\/_\_\/_////\\_\/\\_\_\/_//\
Output
4 22
Solution analysis
- Scan from left to right, stacking the positions of descending edges. An ascending edge at position i closes the latest unmatched descent at j. This matched pair contributes i−j units of area: its two half-unit triangular ends and the intervening strip form that amount.
- Keep a second stack of completed lakes, recording their left boundary and area. When a new matched pair surrounds previous lakes, pop and merge those lakes into the new one. Adjacent basins that only touch at a crest stay separate.
- For the small profile \_/, the descending edge at position 0 matches the ascent at 2 and encloses area 2. In \\//, the inner pair gives area 1 and the enclosing pair contributes 3 more, producing one lake of area 4. The official profile produces four lakes with total volume 22.
Why it works
Last-in-first-out matching pairs each ascent with the descent at the same height that bounds its water layer. These layer areas partition the trapped water. A previously completed basin is part of the same final lake exactly when its boundary lies inside the new enclosing pair, which is precisely what the second stack merges.
Watch out. Unmatched descents or ascents drain away. Do not count every matched pair as a separate lake: nested basins merge. Backslashes in sample data must be preserved literally.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
#include<utility>
using namespace std;
int main(){
string profile;
cin>>profile;
vector<int>descents;
vector<pair<int,long long>>lakes;
for(int i=0;i<static_cast<int>(profile.size());i++){
if(profile[i]==char(92)){
descents.push_back(i);
}
else if(profile[i]=='/'&&!descents.empty()){
int left=descents.back();
descents.pop_back();
long long area=i-left;
// A larger filled basin absorbs all enclosed smaller lakes.
while(!lakes.empty()&&lakes.back().first>left){
area+=lakes.back().second;
lakes.pop_back();
}
lakes.push_back({left,area});
}
}
long long total=0;
for(const auto&lake:lakes){
total+=lake.second;
}
cout<<lakes.size()<<' '<<total<<'\n';
}