KBALANCE - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

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

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 :grinning: :grinning:

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?