One Rope Across the Skyline
National Olympiad — Municipal round (2026 season)
Submission name: rope.cpp
Problem summary
N adjacent unit-width buildings have heights h[i]. The usual route goes from ground at the left of the first building over the complete skyline to ground after the last. One optional rope may connect the left roof corners of i<j only when h[i]≤h[j]; its length is their Euclidean distance, and it may pass through other buildings. Minimize the total route length for each test case.
Input
T, then for each case N and N heights.
Output
The minimum length for each case; relative or absolute error at most 10⁻⁶.
Constraints
1 ≤ T ≤ 7; 1 ≤ N ≤ 10⁶; 1 ≤ h[i] ≤ 10⁶.
Worked example
An independently prepared example for this explanation.
Input
1 5 5 2 1 6 3
Output
16.162278
Solution analysis
- Let prefix[i] be the original skyline distance to the left roof corner of building i, and total the complete original distance. Using a rope i→j gives prefix[i] + hypot(j−i,h[j]−h[i]) + total−prefix[j]. The prefix array includes all vertical climbs and descents and all preceding roof widths.
- For a fixed destination j, an earlier permitted starting building k is always at least as good as a later permitted start i. The original contour from k to i is at least the straight distance between those corners, and the triangle inequality bounds distance(k,j) by distance(k,i)+distance(i,j). Therefore extending the rope backward to k cannot increase the route. Only the earliest building of height at most h[j] needs to be tried.
- Heights are at most one million. Store the earliest index for each exact height, then take prefix minima over the height domain to answer earliest-at-most queries in constant time. Evaluate one rope for every destination and also retain the no-rope route. In the first example the best rope goes from building 1 to building 4: its length is sqrt(10), and the remaining contour costs 13, giving 16.16227766….
Why it works
The distance formula removes exactly the contour portion replaced by a rope. For any fixed destination, the triangle-inequality argument proves that replacing a later feasible start by an earlier feasible start never worsens its route. The height-prefix minimum returns the earliest feasible start, so it dominates every alternative for that destination. Trying all destinations and the option of no rope therefore finds a global optimum.
Watch out. Ropes are permitted through intervening buildings. Endpoints are left roof corners, so their horizontal distance is j−i. Store contour lengths in 64-bit integers before converting for the square root.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<vector>
// Algorithm: Let prefix[i] be the original skyline distance to the left roof corner of building
// i, and total the complete original distance.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tests;
cin>>tests;
cout<<fixed<<setprecision(10);
while(tests--){
int n;
cin>>n;
vector<int>height(n);
int maximum=0;
for(int&value:height){
cin>>value;
maximum=max(maximum,value);
}
vector<int>earliest(maximum+1,n);
vector<long long>prefix(n);
prefix[0]=height[0];
for(int i=0;i<n;++i){
earliest[height[i]]=min(earliest[height[i]],i);
if(i>0){
prefix[i]=prefix[i-1]+1+abs(height[i]-height[i-1]);
}
}
for(int value=1;value<=maximum;++value){
earliest[value]=min(earliest[value],earliest[value-1]);
}
long long total=prefix[n-1]+1+height[n-1];
long double answer=total;
for(int destination=0;destination<n;++destination){
int start=earliest[height[destination]];
long double rope=hypot(static_cast<long double>(destination-start),
static_cast<long double>(height[destination]-height[start]));
answer=min(answer,prefix[start]+rope+total-prefix[destination]);
}
cout<<answer<<'\n';
}
}