KLIP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: S.Manuj Nanthan
Preparer: Souradeep Paul
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

DIFFICULTY:

1757

PREREQUISITES:

Queues

PROBLEM:

You have a binary string S and an integer K. In one move, you can pick a substring of length K and flip all the values in it. Each substring can be chosen at most once. What is the lexicographically minimum string that can be obtained?

EXPLANATION

For the final string to be lexicographically minimum, we would like as many characters of the prefix to be 0 as possible.

That leads to the following strategy:

  • Iterate i from 1 to N
  • If S_i = 0, nothing needs to be done
  • Otherwise, S_i = 1.
    • If i+K-1 \leq N, perform the operation on the substring [i, i+K-1]
    • If i+K-1 \gt N, nothing can be done.

Note that this strategy guarantees that the first N-K+1 characters of the final string will be 0.

Implementing this directly gives us a solution in \mathcal{O}(N\cdot K), which is too slow. However, it can be improved to \mathcal{O}(N) with some observation:

  • Suppose we are at position i. We would like to know whether the i-th character is currently 0 or 1 after the previous operations in order to make our decision.
  • Note that this depends only on the number of previous operations that affected this index. If an even number of operations affected this index, it will be the same character that it originally was, otherwise it will be the opposite character.

Since we are iterating from 1 to N, this means that at position i, we only care about the operations that might have been made at positions i-1, i-2, \ldots, i-K+1 — everything before that definitely doesn’t affect this position.

This information can be represented by a queue:

  • Maintain a queue of operations performed
  • When processing a position i, pop the front of the queue while its value is \lt i-K+1
  • After this, the number of operations affecting i is then exactly the size of the queue.
  • Use this to decide whether to perform the operation starting from i or not.
  • If the operation is performed, push i into the back of the queue.

This runs in \mathcal{O}(N) time in total.

There are other solutions as well, that do not use queues. You may look at the testers’ solutions for these.

TIME COMPLEXITY:

\mathcal{O}(N) per test case.

CODE:

Preparer's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define ordered_set tree<int, nuint_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=1000005;
#define M 1000000007
#define BINF 1e16
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 17500001
#define deb(xx) cout << #xx << " " << xx << "\n";
const int LG = 22;


void solve() {

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int>v(n, 0);
    for(int i = 0; i < n; i++) {
        v[i] = s[i] - '0';
    }
    queue<int>q;
    for(int i = 0; i < n - k + 1; i++) {
        while(q.size() > 0 and q.front() < i) {
            q.pop();
        }
        v[i] = (v[i] + q.size()) % 2;
        if(v[i] == 0) continue;
        v[i] = (v[i] + 1) % 2;
        q.push(i + k - 1);
    }


    for(int i = n - k + 1; i < n; i++) {
        while(q.size() > 0 and q.front() < i) {
            q.pop();
        }
        v[i] = (v[i] + q.size()) % 2;
    }
    string ans(n, '0');
    for(int i = 0; i < n; i++) {
        ans[i] = ('0' + v[i]);
    }

    cout << ans << endl;

}


#undef int 
int main() {
#define int long long int
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("optput.txt", "w", stdout);
#endif


    int T;
    cin >> T;
 
    for(int tc = 1; tc <= T; tc++){
        // cout << "Case #" << tc << ": ";
        solve();
    }


return 0;  
 
}
Tester's code (C++, tabr)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<int> a(n + 1);
        for (int i = 0; i < n; i++) {
            if (i) {
                a[i] ^= a[i - 1];
            }
            if (a[i]) {
                s[i] ^= '0' ^ '1';
            }
            if (s[i] == '1' && i <= n - k) {
                s[i] = '0';
                a[i] ^= 1;
                a[i + k] ^= 1;
            }
        }
        cout << s << endl;
    }
    return 0;
}
Tester's code (C++, utkarsh_25dec)
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
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;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            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,' ');
}
int sumN=0;
void solve()
{
    int n=readInt(1,100000,' ');
    sumN+=n;
    assert(sumN<=300000);
    int k=readInt(1,n,'\n');
    string s=readString(n,n,'\n');
    for(auto ch:s)
    	assert(ch=='0' || ch=='1');
    int cnt[n+1]={0};
    int good[n+1]={0};
    for(int i=0;i<n-k+1;i++)
    {
    	if(i==0)
    		cnt[i]=0;
    	else if(i<k)
    		cnt[i]=cnt[i-1];
    	else
    		cnt[i]=cnt[i-1]-good[i-k];
    	int tmp=cnt[i];
    	tmp%=2;
    	if(tmp==1)
    		s[i]='0'+'1'-s[i];
    	if(s[i]=='1')
    	{
    		good[i]=1;
    		cnt[i]++;
    		s[i]='0';
    	}
    }
    for(int i=n-k+1;i<n;i++)
    {
    	if(i==0)
    		cnt[i]=0;
    	else if(i<k)
    		cnt[i]=cnt[i-1];
    	else
    		cnt[i]=cnt[i-1]-good[i-k];
    	int tmp=cnt[i];
    	tmp%=2;
    	if(tmp==1)
    		s[i]='0'+'1'-s[i];
    }
    cout<<s<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,100,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's code (Python)
for _ in range(int(input())):
	n, k = map(int, input().split())
	s = input()
	ans = []
	moves = []
	ptr = 0
	for i in range(n):
		while ptr < len(moves):
			if moves[ptr]+k <= i:
				ptr += 1
			else:
				break
		cur = 0 if s[i] == '0' else 1
		changes = len(moves) - ptr
		cur ^= changes%2
		if i+k > n:
			ans.append(cur)
		else:
			ans.append(0)
			if cur == 1:
				moves.append(i)
	print(''.join(str(x) for x in ans))

/*
Its beginning not the end.
*/
#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set
#define vi vector
#define pii pair <int, int>
#define vpi vector
#define vpp vector <pair<int, pii>>
#define mii map <int, int>
#define mpi map <pii, int>
#define spi set
#define endl “\n”
#define sz(x) ((int) x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue
#define que_min priority_queue <int, vi, greater>
#define bug(…) __f (#VA_ARGS, VA_ARGS)
#define print(a) for(auto x : a) cout << x << " "; cout << endl
#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1) x *= a;
a *= a;
b >>= 1;
}
return x;
}

template
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename… Args>
void __f (const char* names, Arg1&& arg1, Args&&… args)
{
const char* comma = strchr (names + 1, ‘,’);
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args…);
}

const int N = 200005;

void solve() {

int n, k;
cin >> n >> k;
string s;
cin >> s;
int moves = n - k + 1;
if (n == k)
{
	if (s[0] == '1')
	{
		for (int i = 0; i < n; i++)
		{
			if (s[i] == '0')
			{
				s[i] = '1';
			}
			else
			{
				s[i] = '0';
			}
		}
		cout << s << endl;
		return;
	}
	else
	{
		cout << s << endl;
		return;
	}
}
for (int i = 0; i < n; i++)
{
	if (moves == 0)
	{
		break;
	}
	if (s[i] == '0')
	{
		continue;
	}
	if (s[i] == '1')
	{
		int start = i, end = i, count = 1, flag = 1;
		if (i == n - 1 and k != 1)
		{
			break;
		}
		while (count != k and end < n - 1)
		{
			count++;
			end++;
			if (s[end] == '0' and flag)
			{
				i = end - 1;
				flag = 0;
			}
		}

		// cout << start << " " << end << " " << count << endl;
		if (count != k)
		{
			break;
		}
		else
		{
			for (int j = start; j <= end; j++)
			{
				if (s[j] == '0')
				{
					s[j] = '1';
				}
				else
				{
					s[j] = '0';
				}
			}
			// cout << s << endl;
			moves--;
		}

	}
}
cout << s << endl;

}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

clock_t z = clock();
int t = 1;
cin >> t;
while (t--) solve();

cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

return 0;

}

can someone help to improve this logic it is passing sub task 1 2 5 only 3 and 4 are showing tle please help.

Solved it using segment tree with lazy propagation.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define pr(x) cout << (x) << '\n'
#define prl(x) cout << (x) << ' '
#define f first
#define s second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const long long mod97 = 1e9+7;
const long long INF = (1e18);
// const long long modg = 998244353;
// const int max_i = 2e5+5;
// const long double pi = acos((lld)-1);

class segtree {
private:
    // Functions
    void set(long long i, long long v, long long x, long long lx, long long rx){
        if(rx - lx == 1){
            tree[x] = v;
            return;
        }
        long long m = (lx + rx)/2;
        if(i < m){
            set(i, v, 2*x + 1, lx, m);
        } else {
            set(i, v, 2*x + 2, m, rx);
        }
        tree[x] = tree[2*x + 1] + tree[2*x + 2];
    }

    long long get(long long l, long long r, long long x, long long lx, long long rx){
        // This ensures that our get is always correct
        if(lazy[x] != 0){
            tree[x] += (rx - lx)*lazy[x];

            // Making children lazy
            propogate(x, lx, rx);
        }

        if(lx >= r or rx <= l){
            return 0; // NULL VALUE / NUTERAL VALUE
        }
        if(l <= lx and rx <= r){
            return tree[x];
        }
        long long m = (lx + rx)/2;
        long long s1 = get(l, r, 2*x + 1, lx, m);
        long long s2 = get(l, r, 2*x + 2, m, rx);
        return s1 + s2;
    }

    void op(long long l, long long r, long long v, long long x, long long lx, long long rx){
        // Check for laziness
        if(lazy[x] != 0){
            // Removed the laziness from this node
            tree[x] = (rx - lx)*lazy[x];
            
            // spread laziess to child nodes if it exists
            propogate(x, lx, rx);
        }

        // Useless case
        if(lx >= r or rx <= l){
            return;
        }

        if(l <= lx and rx <= r){
            tree[x] += (rx - lx)*v; 

            // Create then remove the laziness for this node
            lazy[x] += v;              
            
            // spread laziess to child nodes if it exists
            propogate(x, lx, rx);

            // This is what being lazy really means
            return; 
        }

        long long m = (lx + rx)/2;
        op(l, r, v, 2*x + 1, lx, m);
        op(l, r, v, 2*x + 2, m, rx);
        tree[x] = tree[2*x + 1] + tree[2*x + 2];
    }

    void propogate(long long x, long long lx, long long rx){
        if(rx - lx != 1){
            lazy[2*x + 1] += lazy[x];
            lazy[2*x + 2] += lazy[x];
        }
        lazy[x] = 0;
    }

public:
    // Data Members
    vector<long long> tree;
    vector<long long> lazy;
    long long size;

    // Functions
    segtree(long long n){
        size = 1;
        while(size < n) size *= 2;
        tree = vector<long long>(2*size, 0);
        lazy = vector<long long>(2*size, 0);
    }

    void set(long long i, long long v){
        set(i, v, 0, 0, size);
    }

    void op(long long l, long long r, long long v){
        op(l, r, v, 0, 0, size);
    }

    long long get(long long l, long long r){
        return get(l, r, 0, 0, size);
    }
};

void solve(){
    int n, k; cin >> n >> k;
    string a; cin >> a;
    segtree b(n);
    vector<ll> cnt(n, 0);
    for(int i = 0; i < n; i++) {
        if(a[i] == '1') b.set(i, 1);
    }
    for(int i = 0; i < n; i++) {
        if(b.get(i, i + 1) % 2 == 1) {
            if(i + k <= n) {
                b.op(i, i + k, 1);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(b.get(i, i + 1) % 2 == 0) a[i] = '0';
        else a[i] = '1';
    }
    cout << a << '\n';
}   


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    long long T = 1;
    cin >> T; 
    for(long long tc = 1; tc <= T; tc++){
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}```

can anyone please give me the sliding window approach solution ?
which is tutored in the video editorial ?
please !!!

can you explain the approach ?

how did you come up with this approach during the contest ??

Can anyone explain this queue approach properly.

I used queue and strings. Can anybody point out which test cases would fail in this approach? I actually got TLE error. Approach was simple.

#include <iostream>
#include <queue>
using namespace std;

void flip(int i, int k, string& s) {
    for(int j{i}; j<i+k; j++) {
        if(s.at(j) == '0') 
            s.at(j)='1';
        else 
            s.at(j) = '0';
    }
    return;
}

int main() {
	// your code goes here
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t{0};
	cin >> t;
	while(t--) {
	    int n{0}, k{0};
	    cin >> n >> k;
	    string s;
	    cin >> s;
	    queue<char> p;
	    int len = n;
	    int f{0};
	    if((f=s.find("1")) == string::npos || (s.find("1") > (len-k)) ) {
	        cout << s << endl;
	        continue;
	    }

	    for(int i=len; i>0;i--) {
	        if((s.at(len-i) == '1') && (i>=k)) {
	           flip(len-i,k,s);
	        }
	        p.push(s.at(len-i));	        
	    }
	    
	    while(!p.empty()) {
	        cout << p.front();
	        p.pop();
	    }
        cout << endl;
	}
	return 0;
}

Solved it using Sum Range Query for Offline Updates.
Reference: Range Query for Offline Updates
Practice Problem:
Shifting Letters II
Shifting Letters II Solution

Solution:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve(){
    int n, k; cin >> n >> k;
    string a; cin >> a;
    vector<int> upd(n + 1, 0), cnt(n, 0);
    for(int i = 0; i < n; i++) cnt[i] = a[i] == '1';
    
    int cur = 0;
    for(int i = 0; i < n; i++) {
        cur += upd[i];
        if((cnt[i] + cur) % 2 == 1 and i + k - 1 < n) {
            upd[i] += 1, upd[i + k] -= 1;
            cur += 1;
        }
        cnt[i] += cur;
    }
    for(int i = 0; i < n; i++) (cnt[i] % 2 == 1? a[i] = '1': a[i] = '0');
    cout << a << '\n';
 }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int i = 1; i <= T; i++){
        solve();
    }

    return 0;
}

thanks you so much!

see mine.

Thank you so much :innocent: