PROBLEM CODE : SCHEDULE Problem - CodeChef
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
try using fast i/o to get rid of tle
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#write your code from here
}
and also don’t use long long int instead of try with int or long int because of increase of size/memory also leads to tle.
Here you can refer: dummies - Learning Made Easy
i was able to resolve tle as i was not poping the element in == 2 case. now the problem is that the answer is wrong. i saw the approach in editorial via binary search. but dont know why this algo is wrong.
thanks for help. but need to know cases where this algo would be wrong because i tried to use that find the biggest gap and divide in two halves
here is updated approach but WA
#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;
}
int mn=0,mn2=0;
for(int i=0;i<n;i++){
if(i%2){
if(s[i]=='1'){
mn++;
}
if(s[i]=='0'){
mn2++;
}
} else {
if(s[i]=='0'){
mn++;
}
if(s[i]=='1'){
mn2++;
}
}
}
if(k>=mn || k>=mn2){
cout<<1<<endl;
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.size()>0 && tejus.top().first == 2)
{
pair<long long int, pair<long long int, long long int>> zero = tejus.top();
tejus.pop();
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;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t; cin>>t;
while(t–){
int n, k;
string s;
cin>>n>>k>>s;
int mn=0, mn2=0;
for(int i=0;i<n;i++){
if(i%2){
if(s[i]==‘1’) mn++;
if(s[i]==‘0’) mn2++;
}
else{
if(s[i]==‘0’) mn++;
if(s[i]==‘1’) mn2++;
}
}
if(min(mn,mn2)<=k) cout<<“1”<<"\n";
else{
vector a;
int x=1;
for(int i=1;i<n;i++){
if(s[i]!=s[i-1]){
a.push_back(x);
x=1;
}
else x++;
}
a.push_back(x);
int low=2, high=n, mid, res=n;
while(low<=high){
mid=(high+low)/2;
long long value=0;
for(int i=0;i<a.size();i++) value+=a[i]/(mid+1);
if(value<=k) {
if(res>mid) res=mid;
high=mid-1;
}
else low=mid+1;
}
cout<<res<<"\n";
}
}
}
Hope my solution helps you.