Alternating Bits as Distinct Repunits
Autumn Tournament (2019)
Submission name: present10.cpp
Problem summary
Take the n-bit binary number1010... beginning with1. Represent it as a sum of distinct binary repunits1,11,111,... . Print the number of summands, or0 if impossible.
Source clarification. The constant-size suffix reduction is explained in the official editorial: https://infos.infosbg.com/files/Contests/ETI/2019/A/analyses/A5_present10_analysis.docx
Input
One positive integer n.
Output
The number of distinct repunits, or0.
Constraints
1≤n≤2·10^9.
Worked example
Original statement sample, with whitespace restored where PDF extraction joined numbers.
Input
6
Output
4
Solution analysis
- Binary repunits are superincreasing: each exceeds the sum of all smaller repunits. Consequently the largest repunit not exceeding the target is forced, giving a unique greedy representation if one exists.
- Removing the largest repunit from an alternating number removes its leading1 and adds1 to the remaining suffix. While the suffix is long, this simply removes the leading10 pair and increments the low bits independently. Batch these steps until only33or34bits remain.
- For n=6 the ordinary greedy computation gives42=31+7+3+1, so4summands. For huge n, take t=(n−34)/2 or(n−33)/2 according to parity, construct only the final34or33alternating bits, add t, and finish greedy with unsigned64-bit integers. The low33bits can absorb more than2.8billion increments, greater than the number of batched steps.
Why it works
Superincreasing values force every greedy decision. During batching, no carry reaches the retained high boundary: the distance from the alternating33-bit suffix to all ones exceeds every allowed t. Thus the batched target is exactly the residual after tforced greedy choices. Finishing the same forced process either reaches zero or proves impossibility.
Watch out. Do not allocate2billion bits or iterate over n. If the residual cannot be represented, the complete number is impossible; do not output the already-counted batched steps.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Superincreasing values force every greedy decision. During batching, no carry reaches the
// retained high boundary: the distance from the alternating33-bit suffix to all ones exceeds every
// allowed t.
#include<iostream>
using namespace std;
int main(){
long long n;
cin>>n;
long long already=0;
int length=static_cast<int>(n);
if(n>=35){
length=n%2==0?34:33;
already=(n-length)/2;
}
unsigned long long value=0;
for(int i=0;i<length;i++){
value=value*2+(i%2==0?1:0);
}
value+=already;
long long answer=already;
for(int bits=62;bits>=1;bits--){
unsigned long long repunit=(1ULL<<bits)-1;
if(repunit<=value){
value-=repunit;
answer++;
}
}
cout<<(value==0?answer:0)<<'\n';
}