PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: very_slow
Preparer: iceknight1093
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
2426
PREREQUISITES:
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;
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
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) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
else readEoln();
}
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) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
else readEoln();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
input_checker inp;
int t = inp.readInt(1, 1e5); inp.readEoln();
int sum_n = 0;
while (t--) {
int n = inp.readInt(1, 2e5); inp.readEoln();
sum_n += n;
assert(sum_n <= 2e5);
string s = inp.readString(n, n, "01");
inp.readEoln();
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");
}
inp.readEof();
}
