cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2013 · MediumBacktracking

Ambiguous Excess-3 Encoding

National Olympiad — Municipal round (2013 season)

Submission name: coding.cpp

Solve in Editor →

Problem summary

Each decimal digit d was encoded as the ordinary binary representation of d+3, without leading zeros. Given a concatenation of these codes, list all nonnegative integers that could have produced it.

Input

A binary string beginning with 1, of length at most 12.

Output

Every possible original integer in increasing order, one per line; −1 if there are none.

Constraints

At most 12 encoded bits. Original integers use their ordinary decimal representation, without leading zeros.

Worked example

An independently prepared example for this explanation.

Input

10111011

Output

88
230

Solution analysis

  1. Precompute the ten binary words for values 3 through 12. At a current position, try every digit whose word matches the next input bits, then recursively decode the rest.
  2. Do not allow a leading zero unless that zero consumes the complete input. Every recursive step consumes at least two bits, so the search depth is at most six. Sort complete digit strings by length and then lexicographically, which is numeric order.
  3. The sample string splits either as 1011|1011, giving 88, or as 101|110|11, giving 230. The string 11 decodes as 0, whereas 10 matches no complete digit encoding.

Why it works

Every legal decoding is a sequence of matching digit words, so recursion follows it uniquely and records it when all bits are consumed. Conversely every recorded path uses valid words and a valid decimal representation. Sorting gives exactly the required order.

Complexity: O(10·10^(L/2)·L) as a simple conservative search bound, with L≤12; O(L) recursion space plus the output list. Each actual node has at most three word lengths to consider.

Watch out. Leading zeros belong to neither the binary digit codes nor a multi-digit original number. Do not assume one fixed word length.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
// Algorithm: Precompute the ten binary words for values 3 through 12.
using namespace std;
string encoded;
string words[10];
vector<string>answers;
void decode(size_t position,string&digits){
    if(position==encoded.size()){
        answers.push_back(digits);
        return;
    }
    for(int digit=0;digit<=9;digit++){
        const string&word=words[digit];
        if(encoded.compare(position,word.size(),word)!=0){
            continue;
        }
        if(digits.empty()&&digit==0&&position+word.size()!=encoded.size()){
            continue;
        }
        digits.push_back(static_cast<char>('0'+digit));
        decode(position+word.size(),digits);
        digits.pop_back();
    }
}
int main(){
    cin>>encoded;
    for(int digit=0;digit<=9;digit++){
        int value=digit+3;
        while(value>0){
            words[digit].push_back(static_cast<char>('0'+value%2));
            value/=2;
        }
        reverse(words[digit].begin(),words[digit].end());
    }
    string digits;
    decode(0,digits);
    sort(answers.begin(),answers.end(),[](const string&a,const string&b){
        return a.size()!=b.size()?a.size()<b.size():a<b;
    });
    if(answers.empty()){
        cout<<-1<<'\n';
    }
    for(const string&answer:answers){
        cout<<answer<<'\n';
    }
}

Source: Arena Olimpiici ↗