BULBS - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author: Manish Tanwar
Tester: Rahul Dugar
Editorialist: Ritesh Gupta

DIFFICULTY:

Simple

PREREQUISITES:

Greedy, Ad-hoc, Math

PROBLEM:

You are given a binary string S which is the final state of initial string T containing all zeros. To convert T into S, you can apply following operations:

  1. Cut a connection between any adjacent elements of string. You can apply this operation at most K times.
  2. Change the state from 0 to 1 to any of the one group, where the group is defined by the connected elements.
  3. Freeze the state of any particular element. This means if you freeze the state of any element then it should not be able to change its state afterwards.

You have to find the minimum number of operation \space 3 is require to convert string T to S.

QUICK EXPLANATION:

  • We can break the given sequence into groups of 1’s and 0’s.
  • A group continuous 0’s which appears either in start or in the end of the string, can have only one connection with adjacent group of 1’s.
  • So, the K can be used to four ways:
    • Only destroying the connections of groups of 0’s appearing in between the string.
    • One can be used in destroying the group of 0’s appearing in the start of string(if exist) and rest K-1 destroying the connections of groups of 0’s appearing in between the string.
    • One can be used in destroying the group of 0’s appearing in the end of string(if exist) and rest K-1 destroying the connections of groups of 0’s appearing in between the string.
    • two can be used in destroying the group of 0’s appearing in the start and end of string(if exist) and rest K-2 destroying the connections of groups of 0’s appearing in between the string.

EXPLANATION:

Lemma: The K can be used to break the connections of only those bulbs which have different states in the end.

Proof: Let suppose, if we break the connection between two bulbs whose state is same, then we can say that if final state is 1 for both then any how we need to activate them both so it is clear that it is not a good choice else if the state is 0 for both then why we are deactivating them as they are still connected by their nearest right and left active neighbours. Instead, we can deactivate this group of continuous 0 from the it’s right and left neighbour.

If string S starts and ends with 1: In this case, all the groups of continuous 0 identified will need two connections to separate out. So, we can find the size of all possible groups of continuous 0 and disconnect top K/2(integer division) and rest are needed to be deactivated from operation \space 3 (explained in problem). If the size of any group is x then we need to perform x times operation \space 3 to disconnect them from the eclectic circuit.

The rest cases are also handled in a similar way once you handle the start and end side group of continuous 0 separately.

TIME COMPLEXITY:

TIME: O(N)
SPACE: O(N)

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V){os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P){return os << "(" << P.first << "," << P.second << ")";}
#ifndef ONLINE_JUDGE
#define TRACE
#endif
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1){ cout << name << " : " << arg1 << endl; }
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define trace(...) 1
#endif
#define mp make_pair
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define I insert
typedef long double ld;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
 
const int inf = 1e9;
 
int go(vi v, int a, int b, int k){
    if(k < 0) return inf;
 
    v.pb(a); v.pb(b);
    sort(v.begin(), v.end());
    k /= 2;
    int ans = 0;
    for(int i=0;i<-k+(int)v.size();i++) ans += v[i];
    return ans;
}
 
int solve(){
    int n,k; cin>>n>>k;
    string s; cin>>s;
 
    int st = 0, en = n-1;
    while(st < n && s[st]=='0') st++;
    while(en >=0 && s[en]=='0') en--;
 
    if(st == n) return 0;
 
    vi v;
    int last = 0;
    for(int i=st;i<=en;i++){
        if(s[i] == '0') last++;
        else{
            if(last) v.pb(last);
            last = 0;
        }
    }
    if(last) v.pb(last);
 
    int ans = n;
    en = n-1-en;
    ans = min(ans, go(v,st,en,k));
    ans = min(ans, go(v,0,en,k-1));
    ans = min(ans, go(v,st,0,k-1));
    ans = min(ans, go(v,0,0,k-2));
    return ans;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while(t--) cout<<solve()<<'\n';
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
int sum_n=0;
void solve() {
	int n,k;
	n=readIntSp(1,100000);
	sum_n+=n;
	assert(sum_n<=500000);
	k=readIntLn(0,n-1);
	string s;
	s=readStringLn(n,n);
	for(char i:s)
		assert(i=='0'||i=='1');
	vector<int> hol;
	int te=0;
	int fron=0,bak=0;
	for(int i=0; i<sz(s); i++)
		if(s[i]=='1') {
			fron=i;
			break;
		}
	s=s.substr(fron);
	while(s.size()&&s.back()=='0') {
		bak++;
		s.pop_back();
	}
	if(s.empty()) {
		cout<<0<<endl;
		return;
	}
	for(int i=0; i<sz(s); i++) {
		if(s[i]=='0')
			te++;
		else {
			if(te)
				hol.pb(te);
			te=0;
		}
	}
	sort(all(hol));
	reverse(all(hol));
	int sum=accumulate(all(hol),0LL)+fron+bak;
	int ans=sum;
	int an=sum;
	for(int i=0; i*2+1<k&&i<sz(hol); i++)
		an-=hol[i];
	if(k==0) {
		cout<<ans<<endl;
		return;
	}
	k--;
	ans=min(ans,an);
	an=sum-max(fron,bak);
	for(int i=0; i*2+1<k&&i<sz(hol); i++)
		an-=hol[i];
	ans=min(ans,an);
	if(k==0) {
		cout<<ans<<endl;
		return;
	}
	an=sum-fron-bak;
	k--;
	for(int i=0; i*2+1<k&&i<sz(hol); i++)
		an-=hol[i];
	ans=min(ans,an);
	cout<<ans<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=readIntLn(1,1000);
//	int t;
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
int solve1(string s, int k) {
	if(k < 0) {
		return 1e7;
	}
	
	vector <int> v;
 
	int cnt = 0;
 
	for(char i:s) {
		if(i == '1') {
			if(cnt > 0)
				v.push_back(cnt);
 
			cnt = 0;
		} else {
			cnt++;
		}
	}
 
	sort(v.begin(), v.end());
 
	while(k > 1 && v.size() > 0) {
		v.pop_back();
		k -= 2;
	}
 
	int ans = 0;
 
	for(int i:v)
		ans += i;
 
	return ans;
}
 
int solve(string s, int k) {
	string s1;
	bool flag = true;
	int cnt1,cnt2;
	cnt1 = cnt2 = 0;
 
	for(char i:s) {
		if(flag && i == '0') {
			cnt1++;
			continue;
		}
		else {
			flag = false;
			s1.push_back(i);
		}
	}
 
	while(s1.back() == '0') {
		cnt2++;
		s1.pop_back();
	}
 
	return min(solve1(s1, k) + cnt1 + cnt2, min(solve1(s1, k-1) + cnt1, min(solve1(s1, k-1) + cnt2, solve1(s1, k-2))));
 
}
 
int main() {
	int t;
	cin >> t;
 
	while(t--) {
		int n,k;
		cin >> n >> k;
 
		string s;
		cin >> s;
 
		int cnt = 0;
 
		for(char i:s) {
			if(i == '1')
				cnt++;
		}
 
		if(cnt == n || cnt == 0) {
			cout << 0 << endl;
		} else {
			cout << solve(s, k) << endl;
		}
	}
}

Video Editorial

16 Likes

https://www.codechef.com/viewsolution/38073023

Can Someone say me why do I get SIGABRT here…??

Thanks in Advance.

@rishup_nitdgp
please help me out in finding the error for WA.
Thanks in advance…

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 :slight_smile:
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.

My code

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

I have also just seen it and corrected it here

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.