BOP - EDITORIAL

editorial
, , , ,
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Arpit Kesharwani
Tester: Anshu Garg
Editorialist: Arpit Kesharwani

DIFFICULTY:

MEDIUM

PREREQUISITES:

String, Math

PROBLEM:

Given a binary string S, in one operation we can select any substring of size M and flip all its characters. There are Q queries and we can append a 0 or 1 character at the beginning of S in each query, what is the minimum number of operations required to make the string lexicographically minimum after each query.

EXPLANATION:

Below is a simple algorithm to find the minimum number of moves for each query by making the string lexicographically minimum :
– Iterate over string as: for i from 1 to |S|-m+1 (from MSB to LSB)
– If S[i] = 1 then flip all S[j] for j in [i,i+m-1] (all m bits) and add 1 to the ans.

This solution will be too slow ( Time Complexity: O(N*Q)), but the idea will be helpful to reach the actual solution. Before we move to actual solution let’s define few terms:
– s_i = i^{th} character of string S
– g_i=1 if the i^{th} bit of the string will be flipped
– x_i = \oplus(s_t) such that i\%m = t\%m and t \le i.

We will append Q zeroes to the beginning of S initially and will update them with query, we can see from the above algorithm that appending 0's to the beginning of string doesn’t affect the answer.

Now,
g_i = s_i \oplus (g_{i-1}\oplus g_{i-2} \oplus ...\oplus g_{i-m+1}) , \ \ i\le n+1-m
\implies g_{i-1}= s_{i-1} \oplus (g_{i-2}\oplus g_{i-2} \oplus ...\oplus g_{i-m})

\therefore \ \ g_i \oplus g_{i-1} = s_i\oplus s_{i-1}\oplus g_{i-m}\oplus g_{i-1}
\implies g_i = s_i\oplus s_{i-1}\oplus g_{i-m}

Similarly expanding the term g_{i-m},
g_{i-m}=s_{i-m}\oplus s_{i-m-1}\oplus g_{i-2m}

\therefore \ \ g_i=(s_i\oplus s_{i-m}\oplus ...\oplus s_{i-rm})\oplus (s_{i-1}\oplus s_{i-m-1}\oplus ...\oplus s_{i-rm-1})\oplus g_{i-(r+1)m}

If we expand this to the last term we get:
g_i = x_i\oplus x_{(i-1)}

Now the answer to the each query will be sum of all g_i's.

As stated earlier we had appended Q zeroes to the beginning of S initially and will update them with query.

Handling update part can be done as follows:
Let the index of string where update happens be cur\_idx.
If 0 is appended to the front of string then no change is observed in any of the g_i.
If 1 is appended to the string the g_i value of all positions i, such that:

  • i \geq cur\_idx and
  • i\%m = cur\_idx\%m or (i+1)\%m = (cur\_idx)\%m
    is flipped.

As we need sum of all g_i and as cur\_idx decreases with queries, we can store the required information to handle queries in the following arrays:

  • total[0..m-1]: total[r] stores number of index i such that i\%m = r and i \geq cur\_idx
  • plus[0...m-1]: plus[r] stores number of index i such that i\%m = r and i \geq cur\_idx and g_i=1.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>

using namespace std ;

void solve() {
	int n,m,q;
	cin >> n >> m >> q;
	string s, cur_s; 
	cin >> s;
	int x[q]; 
	for(int i=0;i<q;++i) {
		cin >> x[i];
		cur_s += '0';
	}
	cur_s += s;
	
	vector<int> X(m), tot(m), plus(m);
	for(int i=q;i+m-1<cur_s.size();++i) {
		X[i%m] ^= (cur_s[i] == '1');
		tot[i%m]++;
		int v = X[i%m]^X[(i-1+m)%m];
		if(v == 1) plus[i%m]++;
	} 

	int ans = 0;
	for(int i=0;i<m;++i) ans += plus[i];

	for(int i=0,cur_idx=q-1;i<q;++i,cur_idx--) {
		if(x[i] == 1) {
			int t = cur_s.size()-1, r = cur_idx%m;
			tot[r]++;
			int neg = tot[r] - plus[r] ;
			ans += neg - plus[r];
			plus[r] = neg;

			r = (r+1)%m;
			neg = tot[r] - plus[r];
			ans += neg - plus[r];
			plus[r] = neg;
		} else tot[cur_idx%m]++;
		cout << ans << '\n';
	}
}

int main() {
	int t;
	cin >> t;
	while(t--) solve();
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std ;

#define ll              long long 
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }

int _runtimeTerror_()
{
    int n, m, Q;
    cin >> n >> m >> Q;
    string s;
    cin >> s;
    vector<int> a(m), b(m);
    a[(n - m) % m] += s[n - m] == '0';
    b[(n - m) % m] += s[n - m] == '1';
    int ans = b[(n - m) % m];
    for(int i=n-m-1;i>=0;--i) {
    	int cur = s[i] - '0';
        int f = i % m;
    	ans -= b[f];
    	if(cur) {
    		swap(a[f], b[f]);
    		++b[f];
    	}
    	else {
    		++a[f];
    	}
    	ans += b[f];
        f = (f + 1) % m;
    	if(cur) {
    		ans -= b[f];
    		swap(a[f], b[f]);
    		ans += b[f];
   		}
    }
    int i = -1, prev = s[0] - '0';
    for(int id=1;id<=Q;++id) {
    	i = (i + m) % m;
    	ans -= b[i];
    	int cur;
    	cin >> cur;
    	if(cur) {
    		swap(a[i], b[i]);
    		++b[i];
    	}
    	else {
    		++a[i];
    	}
    	ans += b[i];
        int f = (i + 1) % m;
    	if(cur) {
    		ans -= b[f];
    		swap(a[f], b[f]);
    		ans += b[f];
   		}
   		--i;
   		cout << ans << "\n";
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int TESTS;
    cin >> TESTS;
    while(TESTS--) {
        _runtimeTerror_();
    }
    return 0;
}
3 Likes