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:
- Cut a connection between any adjacent elements of string. You can apply this operation at most K times.
- Change the state from 0 to 1 to any of the one group, where the group is defined by the connected elements.
- 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;
}
}
}
