Repeated Skipping of a Sequence
National Olympiad — Municipal round (2022 season)
Submission name: skip.cpp
Problem summary
Filter1…n by retaining indices0,2,4,…, then0,3,6,…, then stride4, and so on. Report the largest survivor before only1 remains.
Input
One integer n.
Output
The maximum of the penultimate sequence.
Constraints
1<n<100000.
Worked example
Input and output for the worked example discussed below.
Input
21
Output
19
Solution analysis
- Store the current survivors in increasing order. At stride k, retain zero-based positions0,k,2k,… . The first value1 survives every stage.
- Remember the current last value before replacing the vector. When the next vector has size one, that remembered value is the answer.
- For21, the relevant stages are [1,3,5,…,21], [1,7,13,19], then[1]. The penultimate maximum is19, not1.
Why it works
Each filter retains exactly the specified current positions and preserves increasing order. The stored last element before the singleton stage is therefore the desired maximum.
Complexity: O(N) total time and O(N) space, because survivor counts at least halve each stage.
Watch out. Stride applies to current positions, not original values.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
// Each filter retains exactly the specified current positions and preserves increasing order.
int main(){
int n;
cin>>n;
vector<int>a(n);
iota(a.begin(),a.end(),1);
int stride=2,answer=n;
while(a.size()>1){
answer=a.back();
vector<int>b;
for(int i=0;i<int(a.size());i+=stride){
b.push_back(a[i]);
}
a.swap(b);
stride++;
}
cout<<answer<<'\n';
}