Mutant Frogs
National Olympiad — National round (2009 season)
Submission name: frogs.cpp
Problem summary
A frog starts on each bale in a line. A jump always goes to the nearest strictly higher bale to the right. If none exists, a further jump reaches the world represented by −1. Given the maximum allowed jumps for each frog, report its greatest reachable height.
Input
N, then N heights Hi, then N jump limits Ji.
Output
N reached heights, using −1 after leaving the line, separated by single spaces.
Constraints
1 ≤ N ≤ 1000000; 1 ≤ Hi ≤ 1000000000; the printed limit is 0 < Ji < N.
Worked example
An independently prepared example for this explanation.
Input
8 3 1 4 5 6 2 3 8 1 2 1 3 4 2 1 2
Output
4 5 5 -1 -1 8 8 -1
Solution analysis
- Read both arrays, then scan bales from right to left. Maintain a stack of indices with strictly decreasing heights from bottom to top. Before processing i, remove every top whose height is at most Hi. The top then is the nearest strictly higher bale to the right.
- The remaining stack, read from top to bottom, is the entire forced jump chain from i: the next-greater bale, its next-greater successor, and so on. Therefore Ji jumps reach stack[size−Ji] when 1 ≤ Ji ≤ size; a larger limit reaches the outside world. Push i after answering its query.
- In the sample the bale of height 5 has chain 6,8. Three jumps therefore leave the line. The height-2 bale has chain 3,8, so two jumps reach 8. Each index is pushed once and popped once, giving a linear solution even for one million bales.
Why it works
Induct from right to left. The stack is the next-greater chain of the most recently processed bale. Removing top heights no greater than Hi discards exactly the bales blocked by i for any future jump chain. The first remaining top is the nearest greater bale, and the rest of the stack is its already established successor chain. Indexing this chain returns the unique Ji-th successor, or the absorbing outside world if the chain is exhausted. Every jump increases height, so this is the maximum reachable height.
Watch out. Pop equal heights as well as lower ones. Read and store all jump limits before the right-to-left pass. Exactly size jumps reach the bottom stack bale; leaving the line requires one more jump.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>height(n),jumps(n),answer(n),stack;
for(int&value:height){
cin>>value;
}
for(int&value:jumps){
cin>>value;
}
for(int i=n-1;i>=0;i--){
// The stack from top to bottom is the forced successor chain.
while(!stack.empty()&&height[stack.back()]<=height[i]){
stack.pop_back();
}
int size=static_cast<int>(stack.size());
if(jumps[i]==0){
answer[i]=height[i];
}
else if(jumps[i]<=size){
answer[i]=height[stack[size-jumps[i]]];
}
else{
answer[i]=-1;
}
stack.push_back(i);
}
for(int i=0;i<n;i++){
if(i!=0){
cout<<' ';
}
cout<<answer[i];
}
cout<<'\n';
}