Longest Nondecreasing Point Route
Autumn Tournament (2007)
Submission name: jumps.cpp
Problem summary
A grasshopper may jump from (x1,y1) to (x2,y2) when x1≤x2 and y1≤y2. Find the maximum number of distinct point locations it can visit without returning to a location. Repeated input coordinates represent the same location.
Input
n, followed by n pairs of nonnegative integer coordinates.
Output
The maximum route length.
Constraints
1≤n≤1000000; coordinates are smaller than 10^9.
Worked example
Original statement sample.
Input
5 3 2 5 0 0 0 6 1 5 0
Output
3
Solution analysis
- Sort point locations by x, breaking ties by increasing y, then erase exact duplicate pairs. Sorting handles the nondecreasing x condition. Equal-x points may legitimately be visited in increasing y order.
- Find a longest nondecreasing subsequence of the remaining y coordinates. tails[len−1] stores the smallest possible ending y for a route of length len. Use upper_bound, which finds the first tail strictly greater than y; equal y values must extend a route rather than replace it.
- The sample’s distinct sorted points are (0,0),(3,2),(5,0),(6,1). Their y values are 0,2,0,1. A nondecreasing subsequence 0,0,1 describes the route (0,0)→(5,0)→(6,1), of length 3. The duplicate (5,0) cannot be counted twice.
Why it works
Any permitted route can be ordered by x and then y; among distinct equal-x locations, increasing y preserves every possible visit. Its y sequence is nondecreasing. Conversely every such subsequence gives a legal route. The standard smallest-tail replacement preserves all possible future extensions and therefore finds the maximum length.
Watch out. Use upper_bound, not lower_bound: both coordinates allow equality. Remove exact duplicate locations, as confirmed by the sample. Sorting equal x by decreasing y would incorrectly prevent valid vertical routes.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<pair<int,int>>points(n);
for(auto&point:points){
cin>>point.first>>point.second;
}
sort(points.begin(),points.end());
points.erase(unique(points.begin(),points.end()),points.end());
vector<int>tails;
for(auto point:points){
// Equality is allowed, so extend past existing equal tails.
auto position=upper_bound(tails.begin(),tails.end(),point.second);
if(position==tails.end()){
tails.push_back(point.second);
}
else{
*position=point.second;
}
}
cout<<tails.size()<<'\n';
}