Keep the Digits 2014
National Olympiad — National round
Submission name: deletion.cpp
Problem summary
Concatenate the decimal representations of 1 through N without separators. Count choices of four retained digit positions, in their original order, spelling 2014; all other digits are removed.
Input
Integer N.
Output
The number of choices.
Constraints
14 ≤ N ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
15
Output
5
Solution analysis
- Maintain counts for matching the first zero through four characters of 2014; the empty match has count one.
- For each generated digit, update matching prefix lengths in descending order.
- The final length-four count is the answer.
Why it works
Every subsequence either omits the new digit or uses it as its last character. The recurrence partitions those cases without overlap.
Complexity: O(N log N) time; O(1) auxiliary space.
Watch out. Count positions, not distinct resulting strings. Use 64-bit counts.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every subsequence either omits the new digit or uses it as its last character. The
// recurrence partitions those cases without overlap.
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
cin>>n;
string target="2014";
long long dp[5]={1,0,0,0,0};
for(int x=1;x<=n;x++){
for(char c:to_string(x)){
for(int k=4;k>=1;k--){
if(c==target[k-1]){
dp[k]+=dp[k-1];
}
}
}
}
cout<<dp[4]<<'\n';
}