This took away lot of brain cells
BTW if Anyone Needs a Hindi Video Editorial - Link
12 Likes
Can someone tell me where did i go wrong ?
Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
string s;
cin>>n>>k;
cin>>s;
int c=0,c1=0,cnt=0;
for(int i=0;i<n;i++)
if(s[i]==‘0’) cnt++;
if(cnt==0 or cnt==n)
{
cout<<“0\n”;
continue;
}
int ans=cnt;
vector v;
int i=0;
while(i<n)
{
if(s[i]==‘0’)
{
c=0;
while(i+c<n and s[i+c]==‘0’)
c++;
i=i+c;
v.push_back(c);
}
else i++;
}
sort(v.rbegin(),v.rend());
int f=0,b=n-1;
i=0;
while(i<n and s[i]==‘0’)
i++,f++;
i=n-1;
while(i>=0 and s[i]==‘0’)
i–,b++;
int y=0,tot=0;
for(int j=0;j<v.size();j++)
{
if(k>0)
{
if(v[j]==f)
{ k–; f=-1; }
else if(v[j]==b)
{ k–; b=-1; }
else
{
if(k>1)
k-=2;
else
{ k=0; tot+=v[j]; }
}
}
else
tot+=v[j];
}
cout<<min(tot,ans)<<‘\n’;
}
return 0;
}
Link for the same : SOLUTION
please provide some tough testcases and answers for it
so that people who have got wrong can examine there solutions
9 Likes
Implemented the same logic, where am I going wrong??
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;
ll required = 0;
for(int i=0; i<n; i++)
if(s[i] == '1')
required++;
if( required == 0)
{
cout<<0<<"\n";
continue;
}
vector<pair<ll,ll>> vec;
ll l = 0,r = 0;
for(int i=0;i<n;i++)
{
if(s[i] == '1')
{
r = i;
if(l==r){
continue;
l = i;
}
else if(r-(l) <=0)
continue;
else if(r == 0)
{
vec.push_back({r - (l+1) , 1});
}else if(l == 0)
{
vec.push_back({r - (l), 1});
}else
{
vec.push_back({r - (l+1),2});
}
l = i;
}
}
if(s[n-1] == '0')
{
vec.push_back({n - (l+1),1});
}
// for(auto x:vec)
// cout<<x.first<<" "<<x.second<<"\n";
sort(vec.begin(),vec.end(), [&](pair<ll,ll> p1, pair<ll,ll> p2){
if(p1.first == p2.first)
return p1.second<p2.second;
return p1.first>p2.second;
});
ll reduced = 0;
ll total = n;
for(auto x:vec)
{
if(k>=x.second)
{
reduced+=x.first;
k-=x.second;
}
}
cout<<max(((total - reduced ) - required),0LL)<<"\n";
}
return 0;
}please tell were iam doing wrong
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repab(i,a,b) for(int i=a;i<=b;i++)
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define printarr(v) for(auto x:v){cout<<x<<" "; }
#define debug1(a) cout<<#a<<" "<<(a)<<endl;
#define debug2(a,b) cout<<#a<<" "<<(a)<<" "<<#b<<" "<<(b)<<endl;
#define debug3(a,b,c) cout<<#a<<" "<<(a)<<" "<<#b<<" "<<(b)<<" "#c<<" "<<(c)<<endl;
typedef long double ld;
void solve()
{
ll n, k;
cin >> n >> k;
string s;
cin >> s;
if (s.length() == 1)
{
cout << 0 << endl;
return;
}
bool temp = false;
vector<bool> vis(n, false);
vector<pair<ll, pair<ll, ll>>> res;
ll start = 0;
ll end = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
{
if (temp)
{
end = i - 1;
temp = false;
res.push_back({end - start + 1, {start, end}});
}
}
else
{
if (!temp)
{
start = i;
temp = true;
}
else
{
end = i;
}
}
}
if (temp)
{
end = n - 1;
res.push_back({end - start + 1, {start, end}});
}
sort(res.rbegin(), res.rend());
for (int i = 0; i < res.size(); i++)
{
if (k <= 0)
{
break;
}
else
{
pair<ll, ll> p = res[i].second;
ll start1 = p.first;
ll end1 = p.second;
if (start1 > 0 && end1 < n - 1)
{
if (k >= 2)
{
for (int j = p.first; j <= p.second; j++)
{
vis[j] = true;
}
k -= 2;
}
}
else
{
if (start1 == 0)
{
for (int j = 0; j <= p.second; j++)
{
vis[j] = true;
}
k--;
}
else if (end1 == n - 1)
{
for (int j = start1; j <= p.second; j++)
{
vis[j] = true;
}
k--;
}
}
}
}
/*for (int i = 0; i < res.size(); i++)
{
cout << res[i].first << " " << res[i].second.first << " " << res[i].second.second << endl;
}
for (auto x : vis)
{
cout << x << " ";
}
cout << endl;*/
ll res1 = 0;
bool temp1 = false, one = false;
ll count = 0;
for (int i = 0; i < n; i++)
{
if (!vis[i])
{
temp1 = true;
if (s[i] == '0')
{
count++;
}
else
{
one = true;
}
}
else
{
if (temp1 && one)
{
res1 += count;
}
temp1 = false;
one = false;
count = 0;
}
}
if (temp1 && one)
{
res1 += count;
}
cout << res1 << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
solve();
}
}
can you make the test case visible 
I am sure my code is right but still it is giving wrong sol.
9 Likes
yes please most of the please are getting wrong
provide some test cases are make testcases visible
@admin @rahuldugar @rishup_nitdgp
1 Like
Try this for a test case
1
9 2
001000100
1 Like
weak test cases
some of the submissions getting correct answer after getting 4 output in this test case
1
9 2
001000100
2 Likes
solution gives AC, even you get wrong on this testcase…
weak test cases
Is the answer 2 ? my code outputs 2.
no answer is 3
3 Likes
can you help me with my code. I have used similar approach as discussed in tutorial but getting WA.
First very common mistake is you are not storing number of zeroes in zt variable that come in the last of string
you have to add
if(z!=0){v.pb(mp(z,1LL));
zt+=z;}
1 Like
try this test case
1
9 2
001000100
In your code vector stores 3,2,2 and removing 3 and decrease k by 2and gives output 4
but if we remove both 2’s and decrease k by 2 (because k decrease by 1 in each case) than answer is 3 and this is correct answer
3 Likes
I have got the point.
Thank you very much for your time.
welcome
1
11 3
00010000100
in this test case your code gives output 0
but the answer is 2
2 Likes