Largest Equal-Run Number
Autumn Tournament (2010)
Submission name: prettynum.cpp
Problem summary
A beautiful number has maximal runs of identical digits of one common length, for example 112233 or 111222111. Among contiguous portions of the given digit sequence, find the largest beautiful decimal number.
Source clarification. The official editorial excludes leading-zero candidates. The source does not specify a separate all-zero case; this implementation safely prints 0 for an all-zero sequence. Editorial: https://infos.infosbg.com/files/Contests/ETI/2010/C/analyses/prettynum_analysis.pdf
Input
N followed by N space-separated digits.
Output
The largest beautiful number as a digit string.
Constraints
3 ≤ N ≤ 1000000.
Worked example
Original statement sample.
Input
8 1 1 1 0 0 2 2 2
Output
110022
Solution analysis
- Compress consecutive equal digits into runs, storing the start and length of each run. A beautiful substring that crosses at least three runs must use every interior run completely, so those interior run lengths must all equal a common k. Only its first and last runs may be shortened to k.
- Group consecutive original runs of equal length k. Take the whole group and extend it by k digits from the previous and next runs when those runs are longer than k. Also consider each single full run. These candidates cover an optimum: any shorter endpoints can be extended to k, and omitting a compatible run cannot improve the number length.
- Compare candidates numerically: first their digit counts, then lexicographically. Do not include a leading zero block; dropping it preserves the beautiful property. Keep candidate start/end positions instead of copying strings. Across all groups, interior lengths total N and each original run serves as a shortened boundary at most twice, so even the character comparisons total O(N).
- The sample has runs 1³,0²,2³. The group consisting of 0² can take two ones from the left run and two twos from the right run, producing 110022. Taking all three original runs would not be beautiful because their lengths differ.
Why it works
For any beautiful substring crossing multiple runs, its fully used interior runs all have the chosen common length k. They lie in one maximal group of equal-length runs, and any usable endpoint is a k-digit suffix or prefix of a neighboring longer run. Expanding to the entire compatible group and both possible boundaries gives a candidate at least as long. Substrings lying inside one run are covered by single-run candidates. Hence some generated candidate is optimal; numeric comparison selects the largest.
Watch out. Do not require the two boundary runs to be used completely. Compare long numbers as strings, never as machine integers. Avoid copying a growing best substring repeatedly. A leading zero block cannot increase a number’s value.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Run{
int start;
int length;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
string digits;
digits.reserve(n);
for(int i=0;i<n;i++){
int digit;
cin>>digit;
digits.push_back(static_cast<char>('0'+digit));
}
vector<Run>runs;
runs.reserve(n);
for(int left=0;left<n;){
int right=left+1;
while(right<n&&digits[right]==digits[left]){
right++;
}
runs.push_back({left,right-left});
left=right;
}
int bestStart=0;
int bestLength=1;
auto consider=[&](int start,int length,int blockLength){
if(digits[start]=='0'){
if(length==blockLength){
length=1;
}
else{
start+=blockLength;
length-=blockLength;
}
}
if(length>bestLength||
(length==bestLength&&digits.compare(start,length,digits,bestStart,bestLength)>0)){
bestStart=start;
bestLength=length;
}
};
for(const Run&run:runs){
consider(run.start,run.length,run.length);
}
int count=static_cast<int>(runs.size());
for(int first=0;first<count;){
int last=first;
int blockLength=runs[first].length;
while(last+1<count&&runs[last+1].length==blockLength){
last++;
}
int start=runs[first].start;
int end=runs[last].start+runs[last].length;
// Only boundary runs may be shortened to the common length.
if(first>0&&runs[first-1].length>blockLength){
start-=blockLength;
}
if(last+1<count&&runs[last+1].length>blockLength){
end+=blockLength;
}
consider(start,end-start,blockLength);
first=last+1;
}
cout<<digits.substr(bestStart,bestLength)<<'\n';
}