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.