PROBLEM LINK:
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.