Author: very_slow
Preparer: iceknight1093
Tester: yash_daga
Editorialist: iceknight1093

2426

None

# PROBLEM:

Given a string S, in one move you can flip two adjacent equal characters in it.
Is it possible to turn S into a string of all zeros, or all ones?

# EXPLANATION:

Let’s check if it’s possible to turn all the characters into 0: the check for 1 will be similar.

Note that we can think of our moves as ‘insertions’ and ‘deletions’ instead: we want to ‘delete’ all the ones from S, and to do that, we can either delete two adjacent ones or insert two adjacent ones.

Observe that each move operates on one even and one odd index; i.e, it either deletes one 1 each from an even and an odd index, or inserts one 1 each from an even and an odd index.
We want to reach a state where there are no 1's in the string; which also means that there are no ones at even or odd indices.
Since their counts increase and decrease together, this is of course only possible if from the very start, S had an equal number of 1's at even positions and at odd positions.
This condition is in fact also sufficient!

Proof

Suppose S has an equal number of ones at even and odd indices.
If S contains no ones, we’re done: that’s exactly the state we want to reach.

Otherwise, there will exist indices i\lt such that:

• S_i = S_j = 1
• i and j have different parity; and
• S_k = 0 for each i \lt k \lt j
That is, there will be two ones in S at different parity positions, with only zeros between them.

Pick such i and j.
Now, i and j have different parity so there’s an even number of zeros between them.
Using the operation, they can all be turned into ones; after which we’ll have an even-sized block of ones (with i and j as its borders) that can be deleted entirely.

We’re now back to the original state of S, except S_i and S_j are 0 instead of 1.
Repeat this process till there are no ones left, and we’re done!

Checking the condition is fairly simple, of course: just count the number of ones at odd and even indices, and check if the counts are equal.
SImilarly, the positions of the zeros will tell you if it’s possible to convert everything to ones.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
if len(s) != n: print(-1)
zero, one = 0, 0
for i in range(n):
if s[i] == '0':
if i%2 == 0: zero += 1
else: zero -= 1
else:
if i%2 == 0: one += 1
else: one -= 1
if zero == 0 or one == 0: print('Yes')
else: print('No')

Tester's code (C++)
// Input Checker
// Input verification
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

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++;
}
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;
}

auto readIntVec(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

auto readLongVec(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

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()
{
ios::sync_with_stdio(false); cin.tie(0);

input_checker inp;

int sum_n = 0;
while (t--) {
sum_n += n;
assert(sum_n <= 2e5);
string s = inp.readString(n, n, "01");
int one=0, zero=0;
for(int i=0;i<n;i++)
{
if(s[i]=='1')
{
if(i&1)
one++;
else
one--;
}
else
{
if(i&1)
zero++;
else
zero--;
}
}
cout<<(zero==0 || one==0 ? "Yes\n" : "No\n");
}
}

1 Like

There is a much simpler implementation using Stack.

Iterate through the string from index 1 to N,
If the char and prevChar are the same, POP from the Stack
If they are different PUSH into the stack.

After the traversal, if the stack has less than 2 elements, ans is ‘Yes’ else ‘No’.

5 Likes

I have a doubt, consider the given test case on the problem i.e.,
0101010
the operations are as follows:
0101010
0011010
0011100
0101100
1001100
1111100
1111111
This is giving the string with all same characters then how the output is “No” for this.
If I’ve done something wrong here, then I would like to get corrected or hear your explanation.
Thanks.

Thanks!!!

1st operation u performed is wrong, read the question carefully: operation can only be applied when two adjacent characters are same

ok my bad include
include
include
using namespace std;
int main() {
int T;
cin>>T;
string v0=“0000000000000000000000000”;
string v1=“1111111111111111111111111”;
string input;
int n,one=-1,zero=-1;
for(int i=1; i<=T; i++){
cin>>n;
cin>>input;
v0=(v0.substr(0,n));
v1=(v1.substr(0,n));
for(int i=0; i<=n; i++){
if(input[i]==‘0’ && input[i+1]==‘1’){
input[i]=‘1’;
input[i+1]=‘1’;
}
if(input[i]==‘1’ && input[i+1]==‘0’){
input[i]=‘1’;
input[i+1]=‘1’;
}
i++;
}
if(input==v1){
cout<<“YES”<<endl;
}
else if(input==v0){
cout<<“YES”<<endl;
}
else {
cout<<“NO”<<endl;
}
}
return 0;
}
this is my code and i don’t know stack. I tried by doing it in other ways. but in my code 101001 is also converted into 111111. can anyone solve this problem then it would helpful to me.

this is my code and i don’t know stack. I tried by doing it in other ways. but my code is also converting 101001 to 111111. can anyone solve this problem then it would helpful to me.*

How can we convert this testcase into all zeros or all ones. For the below case Editorialist’s code give “YES”

10
1010010100

1010010100
1011110111
1000110111
1000000111
1111111111

https://www.codechef.com/viewsolution/1029499583
please suggest me the wrong testcase here

include <bits/stdc++.h>
using namespace std;
define ll long long
define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
define print_any(vec) for(auto value:vec)cout<<value<<" ";
define vect_int vector
define vect_ll vector
define next_line cout<<endl;

void solve(){
int n;
string s;
cin>>n>>s;
string sone;
sone=s;
string szero;
szero=s;
for (int i=0;i<n-1;i++){
if (s[i]==s[i+1]){
sone[i]=‘1’;
sone[i+1]=‘1’;
szero[i]=‘0’;
szero[i+1]=‘0’;
i++;
}
}
int z=1,o=1;
for (int i=0;i<n;i++){
if (sone[i]!=‘1’){
z=0;
}
if (szero[i]!=‘0’){
o=0;
}
}
//cout<<sone<<" “<<szero<<” ";
if (o==1 || z==1){
cout<<“YES”<<endl;
}
else{
cout<<“NO”<<endl;
}
}

int main() {