Minimum Forward Jumps
National Olympiad — National round
Submission name: jumps.cpp
Problem summary
From position 1 in an array, aᵢ permits a jump right by any positive distance at most aᵢ. Find the minimum jumps needed to reach position n.
Input
n, then the n jump limits.
Output
The minimum jumps, or −1 if n is unreachable.
Constraints
2 ≤ n ≤ 3,000,000; 0 ≤ aᵢ ≤ 600. Original memory limit: 5 MB.
Worked example
An independently prepared example for this explanation.
Input
5 2 0 2 0 0
Output
2
Solution analysis
- Reachable positions after at most j jumps form a prefix. Track its endpoint and the farthest endpoint achievable by one more jump.
- Scan each prefix layer, then advance the layer. Read input as a stream to satisfy the memory limit.
Why it works
Every position reachable with at most j+1 jumps is reached from the j-jump prefix. Taking its maximum i+aᵢ computes the next prefix exactly, so the first layer containing n is optimal.
Complexity: O(n) time, O(1) auxiliary space.
Watch out. A zero at the frontier can trap the search; do not allocate a three-million-element array under 5 MB.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every position reachable with at most j+1 jumps is reached from the j-jump prefix. Taking
// its maximum i+aᵢ computes the next prefix exactly, so the first layer containing n is optimal.
#include<iostream>
#include<algorithm>
#include<tuple>
#include<iterator>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
int end=1,far=1,jumps=0;
bool dead=false;
for(int i=1;i<=n;i++){
int a;
cin>>a;
if(dead||end>=n){
continue;
}
if(i>end){
dead=true;
continue;
}
far=max(far,i+a);
if(i==end){
if(far==end){
dead=true;
}
else{
end=far;
jumps++;
}
}
}
cout<<(dead?-1:jumps)<<'\n';
}