Recovering a Faded Sumo Belt Number
National Olympiad — National round (2014 season)
Submission name: kolan.cpp
Problem summary
A digit d is encoded by d painted squares, with one white separator between digits and none at the ends. Exactly one painted square per digit survives fading. Recover the largest and smallest possible numbers.
Input
One binary belt string.
Output
Largest number, then smallest number on separate lines.
Constraints
At most 10000 squares; digits are 1…9; the input has a valid original encoding.
Worked example
Input and output for the worked example discussed below.
Input
0100001000
Output
54 27
Solution analysis
- Every recovered digit block must contain exactly one surviving 1. Separators must be input zeros. Consequently every solution has the same number of digits, equal to the number of surviving 1s.
- Compute suffix feasibility: at start p try block lengths 1…9. A block is legal if it contains exactly one 1 and either reaches the end or is followed by one zero separator and a feasible nonempty suffix. Prefix counts test a block in constant time.
- Reconstruct by taking the largest feasible next digit for the maximum and the smallest for the minimum. Fixed digit count makes lexicographic and numerical order agree. For 0100001000, feasible extremal block pairs have lengths 5,4 and 2,7, yielding 54 and 27.
Why it works
The DP enumerates every legal first block and separator, proving exact suffix feasibility by induction. Among equally long digit strings, the first differing digit decides numerical order; choosing the extremal feasible digit at each step therefore produces the required extremal number.
Watch out. Do not allow trailing white squares, arbitrary-length separators, erased original 1s, or blocks longer than 9. Local greedy choices need suffix feasibility.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
string belt;
cin>>belt;
int length=belt.size();
vector<int>prefix(length+1);
for(int i=0;i<length;i++){
prefix[i+1]=prefix[i]+(belt[i]=='1');
}
vector<bool>possible(length+1,false);
possible[length]=true;
auto nextPosition=[&](int start,int digit){
int end=start+digit;
if(end>length||prefix[end]-prefix[start]!=1){
return -1;
}
if(end==length){
return end;
}
if(belt[end]=='0'&&end+1<length){
return end+1;
}
return -1;
};
for(int start=length-1;start>=0;start--){
for(int digit=1;digit<=9;digit++){
int next=nextPosition(start,digit);
if(next!=-1&&possible[next]){
possible[start]=true;
}
}
}
for(bool maximum:{true,false}){
int start=0;
string answer;
while(start<length){
// A feasible extremal digit decides lexicographic order immediately.
for(int step=0;step<9;step++){
int digit=maximum?9-step:1+step;
int next=nextPosition(start,digit);
if(next!=-1&&possible[next]){
answer+=char('0'+digit);
start=next;
break;
}
}
}
cout<<answer<<'\n';
}
}