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))
