my solution :
the binary search logic:
maxL = 1e6
minL = 1
m = (maxL + minL)/2
now calculate the number of bits need to change/flip to have m as the answer.
if the count is less than k less then the answer can be less than m(even lower than m, so maxl =m ) else m cannot be the answer so answer lies in between m and maxL(minl=m).
in the end minl is the answer
it is simple greedy technique.The longest segment stays on the top of the priority queue, we pop it and divide it by the required factor.Now purpose of a big number is when the top and the second element of the queue are the same i.e suppose we have 4,4.Now we wish to pop that element first which has been divided by a lesser factor.Hence initially we select a big number in the priority queue.
DEVSTR
https://discuss.codechef.com/questions/69954/devstr-editorial
It’s practically the same almost.
2 Likes
Really nice way to solve this. Thanks for sharing your method.
And using “trueval” and “id” is really good. 
Make two strings str0 and str1 that are alternating 0’s and 1’s, str0 starts with 0 and str1 starts with 1.
Now let cnt0 and cnt1.
start comparing your input string str with str0.
if str[i] != str0[1] cnt0++;
similarly compare str and str1 and get cnt1;
Now in variables cnt0 and cnt1 you actually have number of flips required to make string str alternating 0’s and 1’s starting with 0 or 1 respectively.
Now if(k >= min(cnt0, cnt1)) then for sure you can make alternating string.
thus in this case answer is 1.
no code there…
You have split the numbers in 2 halves from middle every-time but that’s not correct.Consider this case 11111 and k=2 then your answer comes out to be 2.But actually answer will be 1 by rearranging the string as 10101.Hope you got this point now 
Your approach is partially correct but not fully correct.
and how we will know about a ?
one can start with a equal to the size of the maximum consecutive block in the initial given string since our answer has to be less than or equal to it .
For a block like 0000000 and flips = 3, 0101010. I think its 0 based, provided u store it similarly.
if block like 000000000 and l=2, we consider zero based indexing the reduced block sould be 001010100 but as M mod (l+1)=0 if we consider the approach proposed at starting without consider the critical case then using that approach we will flip (l+1),2*(l+1)… bits so the answer should be 000100100 but as stated in the editorial in this case boundary value should have got changed.
But the second case works when we consider one based indexing, and reduced block be 001001001. I think there is something missing out in the editorial. Could you figure this out.
Here, the length is 9, which is divisible by l+1. For this case, the pattern is like 001001010, meaning the second last index is changed instead of last one.
Read editorial of devstring, given in comment of the editorial’s post. Its explanation was beautiful.
look at the first three lines of last paragraph and then read my previous comment once again.
I read it. Okay, I see your doubt.
I would say go through editorial of DEVSTR as they are literally the same Q, and that editorial explains it in a better way.
The correct approach was shown in DEVSTR which was flipping bits as usual, except that if we are flipping last bit, we flip second-last instead.
for(long i=0;i<l;i++){
if(i%2==0){
if(s[i]==‘1’){
cnt1++;
}
else{
cnt2++;
}
}
else{
if(s[i]==‘0’){
cnt1++;
}
else{
cnt2++;
}
}
}
Can you please explain me the purpose of this code. Also I am not getting why you wrote this?
It is for handling the case of L=1 as said in the editorial