Div-2 Contest

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




String, Math


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.


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.

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.


Setter's Solution

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');
		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;
			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
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]);
    	else {
    	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]);
    	else {
    	ans += b[i];
        int f = (i + 1) % m;
    	if(cur) {
    		ans -= b[f];
    		swap(a[f], b[f]);
    		ans += b[f];
   		cout << ans << "\n";
    return 0;

int main()
    int TESTS;
    cin >> TESTS;
    while(TESTS--) {
    return 0;