Counting Sawtooth Numbers
National Olympiad — National round (2017 season)
Submission name: saw.cpp
Problem summary
Count n-digit positive integers whose every interior digit is strictly greater than both neighbours or strictly smaller than both.
Source clarification. This 2017 National-round task was shared by Groups C and D; its existing permanent URL is retained.
Input
One integer n.
Output
The exact count of n-digit sawtooth integers.
Constraints
3 ≤ n ≤ 22; the largest answer is 373422269794761171, within signed 64-bit.
Worked example
Input and output for the worked example discussed below.
Input
7
Output
693129
Solution analysis
- The condition means adjacent comparisons strictly alternate up and down. Equal adjacent digits cannot occur. To decide the next allowed digits, only the last digit and the previous comparison direction matter.
- Maintain up[d] and down[d], counts of prefixes ending in d whose last comparison rose or fell. Initialize all two-digit starts with first digit 1…9 and second digit 0…9, skipping equality. The no-leading-zero condition is handled here.
- If next>last, extend a down[last] prefix into nextUp[next]. If next<last, extend up[last] into nextDown[next]. Fresh next arrays prevent a newly generated state from being used again in the same position.
- For length 3 there are 525 valid numbers. A prefix 17 may continue with digits 0…6, while 10 may continue with 1…9. Repeating the transitions through length 7 yields 693129. Sum both direction arrays over all last digits to obtain the final answer.
Why it works
Every valid prefix belongs to exactly one state. Each transition appends exactly a digit that reverses the last strict comparison, so it produces every valid extension once and no invalid extension. Induction from the valid two-digit initialization proves the result.
Watch out. Use strict comparisons and reject equality. Do not allow a leading zero. Initializing a one-digit start with both directions can double-count. Use long long rather than int.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
array<long long,10>up{};
array<long long,10>down{};
for(int first=1;first<=9;first++){
for(int second=0;second<=9;second++){
if(second>first){
up[second]++;
}
else if(second<first){
down[second]++;
}
}
}
for(int length=3;length<=n;length++){
array<long long,10>nextUp{};
array<long long,10>nextDown{};
for(int last=0;last<=9;last++){
for(int next=0;next<=9;next++){
// Strict comparisons must alternate; equal digits are forbidden.
if(next>last){
nextUp[next]+=down[last];
}
else if(next<last){
nextDown[next]+=up[last];
}
}
}
up=nextUp;
down=nextDown;
}
long long answer=0;
for(int digit=0;digit<=9;digit++){
answer+=up[digit]+down[digit];
}
cout<<answer<<'\n';
return 0;
}