# ALTSUFF - Editorial

Author: S. Manuj Nanthan
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh

TBD

Observation

# PROBLEM:

Given a binary string S, you repeat the following operation K times:

• Simultaneously apply the following operation to every index i: if S_i = 1, then set S_i = 0. Further, if S_{i-1} = 0, set it to 1 and if S_{i+1} = 0, set it to 1.

Find the final state of the string.

# EXPLANATION:

Simulate the first operation in \mathcal{O}(N) and reduce K by 1.

After this first move, every position behaves in a very predictable manner. Consider some index i such that S_i = 1. Then, this position will alternate between 1 and 0 in all future moves.

Proof

The first observation is that after a move is made, every 1 in S must be adjacent to a 0.

This can be proved by contradiction. Suppose some 1 is adjacent to only other 1's after a move.
Then, this index was initially 0, and all its neighbors were also initially 0. However, this leaves no way for this index to become 1 after a move is made!
So, every 1 must be adjacent to a 0.

Now the result follows immediately: once an index becomes 1, it has a 0 next to it.
After a move is made, the 1 becomes a 0 and the 0 becomes a 1.
After another move is made, both indices once again swap values.
This continues ad infinitum, regardless of what’s going on in the rest of the string. This completes the proof.

This gives us a simple method of finding the final string:

• For each index i, find the first time it becomes 1. Denote this by first_i.
• This can be done relatively easily: let the position of the closest 1 to the left of i be 1, and the closest 1 on the right be R. Then, the first time position i becomes 1 is \min(i-L, R-i).
• Then, do the following:
• If first_i \gt K, S_i remains 0
• Otherwise, S_i is 1 if K - first_i is even, and 0 otherwise.

Finding L and R for every index can be done in linear time with two scans over the array: one forward and one backward.

# TIME COMPLEXITY

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

# CODE:

Setter's code (Python)
t = int(input())

for _ in range(t):

n,k = map(int,input().split())

r=input().rstrip()

ok = [i for i in r]

for i in range(n):

if( ok [i]=='0' and ( (i!=0 and ok[i-1]=='1') or (i!= n-1 and ok[i+1]=='1'))):

ok[i]='2'

for i in range(n):

if(ok[i]=='1'):

ok[i]='0'

if(ok[i]=='2'):

ok[i]='1'

left = [-1 for i in range(n)]

right = [-1 for i in range(n) ]

for i in range(n):

if(ok[i]=='1'):

left[i]=i

else:

if(i):

left[i]=left[i-1]

for i in range(n-1,-1,-1):

if(ok[i]=='1'):

right[i]=i

else:

if(i!= n-1):

right[i]=right[i+1]

k-=1

if(k):

for i in range(n):

if(ok[i]=='1'):

if(k%2):

ok[i]='0'

else:

d1 ,d2 = -1,-1

if(left[i]!=-1):    #nearest left 1 bit position

d1 = abs(i-left[i])

if(right[i]!=-1):   #nearest right 1 bit position

d2 = abs(i-right[i])

if(d1==-1 and d2==-1):

continue

elif(d1!=-1 and d2!=-1):

d1 = min(d1,d2)

elif(d1 == -1):

d1 = d2

else:

pass

if(d1 > k): # bit remains 0

pass

else:

if((d1-k)%2==0):

ok[i]='1'

res = ''.join(ok)

print(res)

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}

string readString(int minl, int maxl, const string& pattern = "") {
assert(minl <= maxl);
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
int sum_n = 0;
while (tt--) {
sum_n += n;
int k = in.readInt(1, (int) 1e9);
string s = in.readString(n, n, "01");
k--;
string t = s;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
t[i] = '0';
} else if (i > 0 && s[i - 1] == '1') {
t[i] = '1';
} else if (i < n - 1 && s[i + 1] == '1') {
t[i] = '1';
} else {
t[i] = '0';
}
}
swap(s, t);
set<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
st.emplace(i);
}
}
if (k == 0) {
cout << s << '\n';
continue;
}
string ans;
for (int i = 0; i < n; i++) {
auto iter = st.lower_bound(i);
int d = k + 1;
if (iter != st.end()) {
d = min(d, *iter - i);
}
if (iter != st.begin()) {
iter--;
d = min(d, i - *iter);
}
if (d <= k && d % 2 == k % 2) {
ans += "1";
} else {
ans += "0";
}
}
cout << ans << '\n';
}
assert(sum_n <= 1000000);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
t = [0]*n
for i in range(n):
if s[i] == '0':
continue
t[i] = 0
if i > 0 and s[i-1] == '0':
t[i-1] = 1
if i+1 < n and s[i+1] == '0':
t[i+1] = 1
k -= 1
dist = [n+1]*n
prv = -1
for i in range(n):
if t[i] == 1:
prv = i
if prv != -1:
dist[i] = i - prv
prv = -1
for i in reversed(range(n)):
if t[i] == 1:
prv = i
if prv != -1:
dist[i] = min(dist[i], prv - i)
ans = ''
for i in range(n):
first = dist[i]
if first == n+1 or first > k:
ans += '0'
else:
if (k-first)%2 == 0:
ans += '1'
else:
ans += '0'
print(ans)


My code works but I kept getting exceeded time limit error. Please help me to optimize it.

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

void suffer(string& s, int n) {
string temp{s};
for (int i{}; i < n; i++) {
if (s[i] == '1') {
if (i - 1 >= 0 && s[i - 1] == '0')
temp[i - 1] = '1';
if (i + 1 < n && s[i + 1] == '0')
temp[i + 1] = '1';
temp[i] = '0';
}
}
s = temp;
}

int main() {
int t{};
cin >> t;
while (t--) {
int n{};
long k{};
cin >> n >> k;
string s;
cin >> s;
while (k--)
suffer(s, n);
cout << s << '\n';
}
return 0;
}


Can anyone suggest, what is wrong with my approach?

void solve()
{
int n,k; cin>>n>>k; k++;
string s; cin>>s;
if(n==1) {
cout<<"0\n"; return;
}
map<string, int> mp;
int c = 1;
while(1) {
if(mp.find(s)!=mp.end()) break;
string t = s;
mp[t] = c++;
rep(i,0,n) {
if(s[i]=='1') {
t[i] = '0';
if(i-1>=0 and s[i-1]=='0') t[i-1] = '1';
if(i+1<n and s[i+1]=='0') t[i+1] = '1';
}
}
s = t;
}
// for(auto it:mp) {
//     cout<<it.first<<" "<<it.second<<endl;
// }
// cout<<s<<endl;
int l = mp.size();
if(k<=l) {
for(auto it:mp) {
if(it.second==k) {
cout<<it.first<<endl;
return;
}
}
}
k -= l;
k%=2;
int kk = l-(k==(l-k)%2);
for(auto it:mp) {
if(it.second==kk) {
cout<<it.first<<endl;
return;
}
}
}


Your time complexity is O(k*n), which is not sufficient.

After some operations it will repeat and my complexity is not O(k*n)

That was a reply to ih4t3recursion. In your case check this test case:
1
14 5
10011010111000
Correct ans: 01100101010101

This was my first approach too. Even if you fix this bug, it would give you TLE in last Task. That’s because you find first repeatance, but your code will fail on this test case:
10000…0001 (length is 10^5).
Then you will need (10^5)/2 operations (k) to repeatance to appear. This will take O((10^5)*(10^5)/2) roughly O(10^9)

So it’s better to consider thinking about another approach.

@theairo1
Hi there, thanks for your inputs on this problem, they have helped me a lot. I have tried to implement similar approach like @vedant_9 did, and I am also getting correct answer for the testcase you mentioned.
But, in subtasks, no task is getting AC and last one is giving TLE as expected, I want to update my code such that it can at least get the first 5 testcases AC.
Any thoughts or ideas where I might be going wrong?

hey i dont why my code is not executing here in this codechef ide but actually it is running properly in my Offline java eclipse IDE . Here is my code please help !!

It is this error

at codechef.main(Main.java:26)

import java.util.;
import java.lang.
;
import java.io.*;
class codechef
{

public static String toString(char[] a)
{
// Creating object of String class
String string = new String(a);

return string;
}

public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int i=0;
while(i<t)
{
int NK[] = new int[2];
String[] strNums;
for (int k = 0; k < strNums.length; k++)
{
NK[k] = Integer.parseInt(strNums[k]);
}
String s=sc.next();
char[] arr=new char[NK[0]];
s.getChars(0, NK[0], arr, 0);
int K=0;
while(K< NK[1])
{
int c=0;
for(int h=0;h<s.length();h++)
{
if(arr[h]=='1') c++;
}
int[] index=new int[c];
int m=0;
for(int k=0;k<s.length();k++)
{
if(arr[k]=='1') index[m++]=k;
}
for(int l=0;l<c;l++)
{
if(index[l]==0)
{
if(arr[index[l]+1]=='0')arr[index[l]+1]='1';
}
else if(index[l]==s.length()-1)
{
if(arr[index[l]-1]=='0')arr[index[l]-1]='1';
}
else
{
if(arr[index[l]+1]=='0')arr[index[l]+1]='1';
if(arr[index[l]-1]=='0')arr[index[l]-1]='1';
}
}
for(int b=0;b<c;b++)
{
arr[index[b]]='0';
}

K++;
}
i++;
System.out.println(toString(arr));
}

sc.close();

}


}

Cool thanx

If anyone wondering why we need to perform the operation for the first time
try this test case.

1
3 2
110