Runs and Four-Value Windows
Autumn Tournament (2010)
Submission name: seq.cpp
Problem summary
A sequence contains only 1, 2, 4 and 8. Find its longest contiguous run of equal values and the number of contiguous windows of length four containing all four allowed values.
Input
N, followed by N sequence values.
Output
The longest equal run and the number of qualifying four-element windows.
Constraints
4 ≤ N ≤ 10000; each value is 1, 2, 4 or 8.
Worked example
Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.
Input
11 4 8 8 8 1 2 4 8 1 2 2
Output
3 4
Solution analysis
- Keep currentRun, the length of the equal-valued run ending at the current index. If the current value equals the preceding one, increment it; otherwise start a new run of length one. Update longestRun after every element.
- Independently examine each starting position with four available elements. Since allowed values are distinct powers of two, bitwise OR of the four entries equals 15 exactly when 1, 2, 4 and 8 are all present. Four positions containing all four values must contain each once. An explicit four-value frequency array would also work.
- In the sample, the three adjacent 8s form the longest run. The valid windows are 8 1 2 4, 1 2 4 8, 2 4 8 1 and 4 8 1 2, so the answer is 3 4.
Why it works
The run recurrence counts exactly the equal suffix at each position, so its maximum covers every run. Every length-four window is checked once; OR is 15 precisely when all four required bits occur.
Watch out. Do not count noncontiguous subsequences. Include overlapping windows. The OR test relies on the restricted values and the window length of four.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>values(n);
for(int&value:values){
cin>>value;
}
int currentRun=0;
int longestRun=0;
int windows=0;
for(int i=0;i<n;++i){
if(i>0&&values[i]==values[i-1]){
++currentRun;
}
else{
currentRun=1;
}
longestRun=max(longestRun,currentRun);
if(i+3<n){
// Each allowed value contributes a different bit.
int mask=values[i]|values[i+1]|values[i+2]|values[i+3];
if(mask==15){
++windows;
}
}
}
cout<<longestRun<<' '<<windows<<'\n';
}