KBALANCE - Editorial

Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

EASY

None

PROBLEM:

A binary string S of length N is said to be a K- balanced string if for every index i where S_i= 1 , there must exist an index j where 1 \leq j \leq N and \mid i-j \mid = K . We need to find the minimum number of operations to convert S into a K - balanced string where in a single operation we can choose any index i and flip the value at i.

QUICK EXPLANATION:

• Split the string S into K strings and store them in array vals where
vals_i = S_iS_{i+k}S_{i+2k} \dots for 0 \leq i \lt K .

• Now the final answer will sum over the minimum number of operations for each i to convert vals_i into a 1- balanced string.

• To convert some string T into a 1- balanced string, we could iterate over i from 1 to N. If T_i =1 and none of the neighbors of T_i have value 1, we need to flip T_{i+1} if that index exists or else we can flip T_i .

EXPLANATION:

First let us solve the simpler version of the problem i.e, minimum number of operations to convert S into 1- balanced string. Then, if S_i=1, we need to have either S_{i-1}=1 or S_{i+1} = 1. To change S into a 1-balanced string, we need to apply the following procedure:

• Iterate over i from 1 to N, suppose we encounter some S_i = 1, and no existing neighbour of it (i-1 or i+1) has a value equal to 1. Now we could either flip S_i or flip any of its neighbours. But it would be always optimal to flip S_{i+1} in this scenario because it would benefit another index i+2 if it exists with value S_{i+2}=1 and none of i+2's neighbours have value equal to 1. ( For example to convert 0101 into 1- balanced string, it would be optimal convert the string to 0111 with 1 operation rather than converting it to 0000 using 2 operations) . If the index i+1 doesn’t exist we can flip the value S_i .

Now we know how to convert string S into a 1- balanced string . But how do we convert into a K- balanced string ? The key idea lies in the fact of splitting string into and array vals of K strings where vals_i = S_iS_{i+k}S_{i+2k}\dots for 0 \leq i \lt K. The reason we want to split is that if we look at some index i, it is only interacted by indices i-k and i+k.

Now the problem reduces to finding minimum number of operations to convert each string in vals into a 1- balanced string and then summing those values.

TIME COMPLEXITY:

O(N) for each testcase.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int cost_for_1_balanced(string &s)
{
int n = s.size();
int cost = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
{
if (i - 1 >= 0 && s[i - 1] == '1')
continue;
if (i + 1 < n && s[i + 1] == '1')
continue;

if (i + 1 < n)
s[i + 1] = '1';
else
s[i] = '0';

cost++;
}
}
return cost;
}

int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n, k;
cin >> n >> k;
string s;
cin >> s;

vector<string> vals(k);
for (int i = 0; i < n; i++)
vals[i % k].push_back(s[i]);

int ans = 0;
for (int i = 0; i < k; i++)
ans += cost_for_1_balanced(vals[i]);

cout << ans << endl;
}

return 0;
}

Setter's solution
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif

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;
}
// deb(l, r, 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, ' ');
}
///////////////////////////////////////////////////////////////////////

void solve() {
int n = readIntSp(2, 100000);
int k = readIntLn(1, n);
string s = readStringLn(n, n);
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
if ((i >= k && s[i - k] == '1') || ((i + k) < n && s[i + k] == '1')) {
;
} else {
ans++;
if (i + k < n) s[i + k] = '1';
}
}
}
cout << ans << '\n';
}

signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = readIntLn(1, 100000);
while (t--) {
solve();
}
assert(getchar() == -1);
return 0;
}


Tester's solution
#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;
cin>>n>>k;
string s;
cin>>s;
int ans = 0;
for(int i = 0; i < n; i++){
if(s[i] == '1'){
if(i - k > -1 && s[i - k] == '1'){
continue;
}
if(i + k < n){
if(s[i + k] == '0'){
s[i + k] = '1';
ans++;
}
}else{
ans++;
}
}
}
cout<<ans<<"\n";
}
return 0;
}


Please comment below if you have any questions, alternate solutions, or suggestions.

2 Likes

I have a query related to this problem, In the test case 5 3 11110 The sample output says the min no of operations is 2. But, can’t we convert 1111’0’ to 1111’1’ and make it a 3-balanced string in single operation? Please clarify this.

Hey, 11111 is not a 3-balanced string because if you look at the middle digit 1, (index i = 3), there should either exist an index i-3=0 equal to 1 or i+3=6 equal to 1. But since these indices themselves do not exist, 11111 is not a 3-balanced string.

3 Likes

ohh okay, Thanks @ajit123q . So those indices where i+k and i-k do not exist, they must definitely be 0 in order to make a balanced string right?

Can somebody plz tell why this solution is wrong? Any test case where this sol goes wrong?

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 100000000000000000
#define ll long long
#define ld long double
#define pb push_back
#define pi 3.141592653589793238462643383279502884197169399375105820974944592307816406286
#define eps 1e-7
string alpha="abcdefghijklmnopqrstuvwxyz";
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1,tt=0;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
string st;
cin>>st;
int i=0,ans=0;
while(i<n){
if(st[i]=='1'){
if(i-k>=0&&st[i-k]=='1'){

}else if(i+k<n&&st[i+k]=='1'){

}else if(i+k<n&&st[i+k]=='0'){
ans++;
st[i+k]=='1';
}else if(i-k>=0){
st[i-k]='1';
ans++;
}else{
st[i]='0';
ans++;
}
}
i++;
}
cout<<ans;
cout<<endl;
}
return 0;
}


Check For the INPUT:-

1
9 2
000100010

Correct:- 1
Yours:- 2

2 Likes

What is wrong with my code can someone give a tc where my code fails…
https://www.codechef.com/viewsolution/51456809

Thanks for the input…The answer is incorrect because in 3rd condition in the while loop i have written the statement st[i+k]==‘1’ rather than st[i+k] =‘1’.

1 Like

this is the error, if we have done in our code we are like just one extra equal in my code make my code != AC

1 Like

why should we split the string to k length strings?
how do we get k balanced string by making sub-strings as 1 balanced string?

               vals[i % k].push_back(s[i]);



Setter’s solution
[/quote]
Can anyone explain this snippet from setter solution.

I have a doubt on editorialist solution.
why did we do
vals[i % k].push_back(s[i]);
@ajit123q
can you explain this

Because that’s the definition of vals in the Editorial:

vals_i = S_iS_{i+k}S_{i+2k} \dots for 0 \leq i \lt K

if you check for i=2 there should 1 at either of( i=-1 or i=5) ,which gives index out of bond error.

1 Like

@ssjgz so can we give any definition to it according to our choice like making the '1st val a string with n//k terms second with next n//k and so on and last one with n//k+n%k variables

I have a query about he testers code, i want to know how is the case where the k+i < n and s[k+i] == 1 is handled?