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
links are broken. please fix them
In this problem my observation is: if k>=(n//2)+1 then the answer should be 1, but I can see that there are cases which gives wrong answer on this logic, can anyone please help me what could be the reason behind it.
can anyone tell me what’s wrong in this approach…
thanks in advance…
https://www.codechef.com/viewsolution/32560135
The crucial observation is that for any L and any block of A with length M,ceil(M/(L+1)) flips are necessary to convert that block into a substring without blocks of length greater than L
Can someone please explain what is the intuition behind this? And how exactly did we reach to this conclusion?
i tried to use heap , where the elements are stored in following way
length of block , start of block and end of block;
if(length of block is > 2){
POP THE ELEMENT AND DIVIDE IN BETWEEN,
}
IF(length ==1){
break;//answer is 1
}
if(length==2){
if start ==0 or end==s.length()-1:
we can divide in 1 1
}
else {answer is 2}
#include <bits/stdc++.h> using namespace std; int main() { long long int t; cin >> t; while (t--) { long long int n, k; cin >> n >> k; string s; cin >> s; if(n==1){ cout<<"1\n";continue; } priority_queue<pair<long long int, pair<long long int, long long int>>> tejus; long long int current = 0; while (current < n) { long long int start = current; long long int end = current; while (s[current] == s[start] && current < n) { current++; end++; } current = end; end--; long long int kitne = end - start + 1; tejus.push({kitne, {start, end}}); //cout<<s[start]<<" "<<start<<" "<<end<<"\n"; } while (tejus.size() > 0 && k > 0) { pair<long long int, pair<long long int, long long int>> temp = tejus.top(); //cout<<temp.first<<" "<<temp.second.first<<" "<<temp.second.second<<"\n"; tejus.pop(); if (temp.first == 1) { break; } else if (temp.first > 2) { long long int left = temp.second.first; long long int right = temp.second.second; long long int middle = (left + right) / 2; long long int kitne1 = middle - left; long long int kitne2 = right - middle; tejus.push({kitne1, {left, middle - 1}}); // cout<<"kitne "<<kitne1<<" l "<<left<<" r "<<middle-1<<"\n"; tejus.push({1, {middle, middle}}); // cout<<"kitne "<<1<<" l "<<middle<<" r "<<middle<<"\n"; tejus.push({kitne2, {middle + 1, right}}); // cout<<"kitne "<<kitne2<<" l "<<middle+1<<" r "<<right<<"\n"; k--; } else if (temp.first == 2) { vector<pair<long long int, pair<long long int, long long int>>> bani; bani.push_back(temp); while (tejus.top().first == 2) { pair<long long int, pair<long long int, long long int>> zero = tejus.top(); bani.push_back(zero); } int df = bani.size(); for (int i = 0; i < bani.size(); i++) { if (bani[i].second.first == 0 || bani[i].second.second == s.length() - 1) { df--; long long int left = bani[i].second.first; long long int right = bani[i].second.second; tejus.push({1, {left, left}}); tejus.push({1, {right, right}}); k--; } else { tejus.push(bani[i]); } } break; } } pair<long long int, pair<long long int, long long int>> temp = tejus.top(); cout << temp.first << "\n"; //cout<<"outside "<<temp.first<<" "<<temp.second.first<<" "<<temp.second.second<<"\n"; } return 0; }
this answer is wa as well as tle as well as ac.
plz help where is mistake in this approach
Why there is (g-mid) instead of (g) in the first tester’s solution?
Hey @mdamir 
Thanks for asking your doubt.
Think as you have a wooden block of size g and you have to divide it into ‘mid’ sizes by cutting it. Each cut decreases the size by 1.
So if g=7 and mid=3 then you have to just cut it once and it divides into 2 parts each of length 3. As the last part has no need to divide that is why (g-mid) is used.