Repeated Reduction of a Uniform Binary String
Autumn Tournament (2013)
Submission name: niz.cpp
Problem summary
A uniform binary string begins with 1, has no adjacent ones, has at least as many zeros as ones, and its maximal zero runs differ in length by at most one. Repeatedly remove the ones, replace the less frequent zero-run length by 1 and the other length by 0, and rotate to the first 1 if any. On equal frequencies the shorter runs become 1. Report how many reductions occur before the first nonuniform string, followed by its first 50 characters.
Input
One nonempty binary string.
Output
The number of reductions and the first at most 50 characters of the resulting nonuniform string.
Constraints
Length ≤ 500000.
Worked example
Original statement sample.
Input
10010100
Output
2 0
Solution analysis
- Scan maximal zero runs and count zeros and ones. Check the starting character, adjacency rule, count inequality, and the minimum/maximum positive zero-run lengths. Do this before every reduction: the original string may already be nonuniform.
- If both possible run lengths occur, count them. Label the rarer length 1; if counts tie, label the shorter one 1. If all zero runs have the same length, every run becomes 0, as in the source example 100 → 0. Build the next string in the order of the runs, then rotate its prefix before the first 1 to its end.
- For 10010100 the zero-run lengths are 2,1,2. The length-one run is rarer, so the new bits are 010; rotating gives 100. Its only zero run becomes 0, which is not uniform. Output 2 0. Each reduction has at most half as many symbols as its input, so repeated scans remain linear overall.
Why it works
The scan extracts exactly the maximal zero runs specified by the operation. Frequency comparison and the tie rule produce the required labels, and rotating to the first 1 is precisely the first permitted cyclic shift. Induction therefore gives the correct string after every reduction; testing uniformity first stops at the required first failure.
Watch out. Do not require a trailing zero: the definition only restricts the first character and adjacent ones. Compare positive maximal zero-run lengths. Count zero reductions when the input is already invalid. Rotate only when the new string contains 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool uniform(const string&text,vector<int>&runs){
runs.clear();
if(text.empty()||text.front()!='1'){
return false;
}
int ones=0;
int zeros=0;
for(int i=0;i<static_cast<int>(text.size());){
if(text[i]=='1'){
if(i>0&&text[i-1]=='1'){
return false;
}
ones++;
i++;
}
else{
int start=i;
while(i<static_cast<int>(text.size())&&text[i]=='0'){
i++;
}
runs.push_back(i-start);
zeros+=i-start;
}
}
if(ones>zeros||runs.empty()){
return false;
}
return *max_element(runs.begin(),runs.end())-*min_element(runs.begin(),runs.end())<=1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string text;
cin>>text;
vector<int>runs;
int reductions=0;
while(uniform(text,runs)){
int shortest=*min_element(runs.begin(),runs.end());
int longest=*max_element(runs.begin(),runs.end());
int shortCount=count(runs.begin(),runs.end(),shortest);
int longCount=static_cast<int>(runs.size())-shortCount;
int oneLength=shortCount<=longCount?shortest:longest;
string next;
for(int length:runs){
// One run length only means every run receives the common label 0.
next.push_back(shortest!=longest&&length==oneLength?'1':'0');
}
size_t firstOne=next.find('1');
if(firstOne!=string::npos){
rotate(next.begin(),next.begin()+firstOne,next.end());
}
text=next;
reductions++;
}
cout<<reductions<<' '<<text.substr(0,50)<<'\n';
}