PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given a binary string S, you can perform the following types of operations on it:
- Delete any character from S; or
- Choose an index i and flip S_i, i.e, convert it to 0 from 1 and vice versa.
Find the lexicographically minimum possible final string S if you can perform at most K operations.
EXPLANATION:
First, we must decide how many moves we should perform; since we can make at most K.
It’s not hard to see that it is, in fact, optimal to always make K moves.
Why?
Suppose we make strictly less than K moves, and obtain the string A as a result.
Since there’s at least one move remaining, we can use one move to delete the last character of A to obtain a string that’s lexicographically smaller than A; so using less than K moves is never optimal.
Now that we know we’re going to make K moves, we need to decide what to do with them.
It can be observed that:
- If S has more than K ones, it’s not possible to remove all the ones from S (since each move can remove at most one of them).
In this case, the best thing we can do is convert the first K ones of S into zeros. - If S has \leq K ones, it’s possible to remove all of them (either via deletion or by turning them into zeros); and end up with a string consisting of only zeros.
When a string has only zeros, it’ll be lexicographically minimum when it’s as short as possible.
Clearly, the shortest possible string we can attain is just N-K zeros (by using one deletion move each time); and so this is the answer.
tl;dr:
- If S contains \geq K ones, convert the first K of them to zeros.
- If S contains \lt K ones, the answer is N-K zeros.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
cin>>kitne_cases_hain;
assert(1<=kitne_cases_hain && kitne_cases_hain<=1e5);
ll sum=0;
while(kitne_cases_hain--){
ll n,k;
cin>>n>>k;
assert(1<=n && n<=2e5);
assert(0<=k && k<n);
sum+=n;
string s;
cin>>s;
assert(s.size()==n);
ll cnt=0;
for(int i=0;i<n;i++){
assert(s[i]=='0' || s[i]=='1');
if(s[i]=='1'){
cnt++;
}
}
if(cnt<=k){
for(int i=0;i<n-k;i++){
cout<<"0";
}
cout<<"\n";
}else{
for(int i=0;i<n;i++){
if(k==0){
break;
}
if(s[i]=='1'){
k--;
s[i]='0';
}
}
cout<<s<<"\n";
}
}
assert(sum<=2e5);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
s = list(input())
o = s.count('1')
if k >= o: print('0'*(n-k))
else:
for i in range(n):
if s[i] == '1' and k > 0:
s[i] = '0'
k -= 1
print(''.join(s))
