Proficient.
Put your skills to the test.

Problem summary

A code is a nonempty digit string beginning with a nonzero digit. Its decoded number is the smallest positive integer whose ordinary decimal representation is not a subsequence of the code. Find that number, then the numerically smallest code decoding to it; shorter codes precede longer ones.

Constraints

Input length≤2000; the decoded number can exceed built-in integer ranges.

Worked example

An independently prepared example for this explanation.

112039814112723456789

30
120123456789

Solution analysis

1. Build next[i][d], the next occurrence of digit d at or after i. Let missing[i] be the shortest nonempty digit word absent as a subsequence of suffix i. A missing digit gives length 1; otherwise choosing d gives 1+missing[next[i][d]+1]. Compute lengths backward. Reconstruct the shortest absent positive word by trying digits 1..9 for its first digit and 0..9 thereafter, always choosing the smallest digit attaining the remaining optimal length.
2. For the minimal code of number a0a1…ak, begin with digits 1 through a0−1. For each adjacent pair a,b append a barrier block. If a>b, append b,b+1,…,a then all other digits increasingly. If a=b, append a then every other digit increasingly. If a<b, append b,a then all digits except b increasingly; a appears twice. Finally remove an initial zero if present. The sole empty-result case, number 1, uses code 2.
3. The barriers force the next missing digit while preserving all smaller numbers. When a<b, an extra copy of a is necessary to represent the smaller repeated-prefix alternative. For 30, the prefix is 12 and the 3→0 block is 0123456789, yielding 120123456789. For 420 the blocks are 2340156789 and 0123456789 after prefix 123, matching the second official example.

Why it works

Greedy subsequence matching always takes the earliest occurrence of each chosen digit, so the suffix recurrence gives exact shortest absent-word lengths. Choosing smallest eligible digits yields the numerically smallest absent positive integer. For its code, separate successive mandatory complete digit blocks by the greedy matches of its prefixes. All smaller first digits must precede these blocks; each block must contain every digit to preserve all shorter alternatives. Its pivot a must precede all digits below b, while b cannot occur after that pivot before the next block. If a<b this forces a second a. These requirements give the block lengths above; moving every unconstrained digit as early as its order permits gives precisely the stated lexicographically least blocks. A leading zero is unnecessary for positive representations and is removed. Thus the constructed code has minimum length and then minimum value.

Watch out. The answer is a decimal string, not a 64-bit number. Its first digit cannot be zero. Minimize code length before lexical order, handle equal adjacent decoded digits, and preserve the nonempty-code rule for decoded number 1.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
#include<array>
#include<algorithm>
// Algorithm: Build next[i][d], the next occurrence of digit d at or after i.
using namespace std;
int main(){
    string code;
    cin>>code;
    int length=static_cast<int>(code.size());
    vector<array<int,10>>next(length+1);
    next[length].fill(-1);
    vector<int>shortest(length+1,1);
    for(int i=length-1;i>=0;i--){
        next[i]=next[i+1];
        next[i][code[i]-'0']=i;
        shortest[i]=length+2;
        for(int digit=0;digit<=9;digit++){
            int occurrence=next[i][digit];
            int candidate=occurrence==-1?1:1+shortest[occurrence+1];
            shortest[i]=min(shortest[i],candidate);
        }
    }
    int remaining=length+2;
    for(int digit=1;digit<=9;digit++){
        int occurrence=next[0][digit];
        remaining=min(remaining,occurrence==-1?1:1+shortest[occurrence+1]);
    }
    string number;
    int position=0;
    while(true){
        bool finished=false;
        for(int digit=number.empty()?1:0;digit<=9;digit++){
            int occurrence=next[position][digit];
            int candidate=occurrence==-1?1:1+shortest[occurrence+1];
            if(candidate==remaining){
                number.push_back(static_cast<char>('0'+digit));
                if(occurrence==-1){
                    finished=true;
                }
                else{
                    position=occurrence+1;
                    remaining--;
                }
                break;
            }
        }
        if(finished){
            break;
        }
    }
    string minimal;
    for(char digit='1';digit<number[0];digit++){
        minimal.push_back(digit);
    }
    for(size_t i=1;i<number.size();i++){
        char a=number[i-1];
        char b=number[i];
        if(a>b){
            for(char digit=b;digit<=a;digit++){
                minimal.push_back(digit);
            }
            for(char digit='0';digit<='9';digit++){
                if(digit<b||digit>a){
                    minimal.push_back(digit);
                }
            }
        }
        else{
            minimal.push_back(b);
            if(a<b){
                minimal.push_back(a);
            }
            for(char digit='0';digit<='9';digit++){
                if(digit!=b){
                    minimal.push_back(digit);
                }
            }
        }
    }
    if(!minimal.empty()&&minimal[0]=='0'){
        minimal.erase(minimal.begin());
    }
    if(minimal.empty()){
        minimal="2";
    }
    cout<<number<<'\n'<<minimal<<'\n';
}