Nearest Earlier Day with Lower Income
Autumn Tournament (2018)
Submission name: report.cpp
Problem summary
For every day, find the nearest earlier day with strictly smaller income. Days are numbered from 1; output 0 when none exists.
Input
N, then the N daily incomes.
Output
N indices separated by spaces; the original format also places a space after the final index.
Constraints
1 ≤ N ≤ 100000; 1 ≤ income ≤ 1000000.
Worked example
Original statement sample.
Input
5 2 5 3 4 5
Output
0 1 1 3 4
Solution analysis
- Keep a stack of candidate day indices whose incomes are strictly increasing. Before handling day i, remove the top while its income is greater than or equal to today’s. The remaining top, if any, is the answer.
- Why can a removed day never be needed later? Today is closer to every future day and has income no greater than that removed candidate. Whenever the old day would qualify as strictly smaller than a future income, today would also qualify and be nearer. Then push today.
- For 2,5,3,4,5, day 1 has answer 0 and day 2 sees day 1. At day 3, remove day 2 because 5≥3, revealing day 1. Days 4 and 5 then see days 3 and 4, producing 0 1 1 3 4.
Why it works
After removing ineligible candidates, all surviving indices have smaller income than today, and the top is the most recent. Removed indices are permanently dominated by a later day of no greater income. Thus the stack top is precisely the nearest qualifying day.
Watch out. Pop equal incomes too, because the condition is strictly smaller. Store indices, not just values, and use 1-based output positions.
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>income(n+1);
vector<int>candidates;
for(int day=1;day<=n;day++){
cin>>income[day];
while(!candidates.empty()&&income[candidates.back()]>=income[day]){
candidates.pop_back();
}
// The newest surviving candidate is the nearest smaller value.
cout<<(candidates.empty()?0:candidates.back())<<' ';
candidates.push_back(day);
}
cout<<'\n';
}