PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given a binary string S, you can reverse at most one of its substrings. Is it possible to obtain an alternating string?
EXPLANATION:
If S is already alternating, of course the answer is immediately Yes, so let’s deal with the case when it isn’t.
Call an index i bad if S_i = S_{i+1}.
S is alternating if and only if it has no bad indices.
Now, suppose that x is a bad index in S.
Observe that the only real choices we have are to either reverse a substring ending at x, or a substring starting at x+1.
Why?
If the chosen substring starts after x+1 or ends before x, (x, x+1) doesn’t get modified at all; and since they’re equal, the final string will contain adjacent equal elements which we don’t want.
If the chosen substring contains both x and x+1, they’ll move to a different location but the reversal will keep them next to each other; so again the final string will contain adjacent equal elements.
So, the chosen substring can’t avoid x and x+1 entirely, nor can it contain both.
This means it must contain exactly one of them - which is possible only if it ends at x or starts at x+1.
Now, there are a couple of possibilities.
First, suppose there are at least two bad indices - say x and y (with x \lt y).
Then, the only way to choose a substring that affects them both, is to choose [x+1, y] - after all, a substring ending at x won’t affect y, and similarly a substring starting at y+1 won’t affect x.
There’s now a unique substring reversal to check: simply reverse it and check whether S becomes alternating in linear time.
If there are more than two bad indices, choose any two of them as x and y - it won’t affect the answer (because if there are more than two, the answer is always No).
This leaves us with the case when there’s only a single bad index, say x.
Note that the string is alternating till x, and also from x+1 onwards.
So, there are only two possibilities to check for reversals:
- Reverse the prefix [1, x], or
- Reverse the suffix [x+1, N].
To see why: suppose we reverse [L, x]. Then, since the string till x is alternating,
- If S_L = S_x, S doesn’t actually change at all.
- If S_L \neq S_x, the alternating nature of the prefix means S_x = S_{L-1}; so after the reversal index L-1 will be bad.
The only way to prevent this is for L to equal 1, in which case there’s no previous element.
With only two cases to check, simply try both by directly simulating, and see if either of them result in an alternating string.
If you write a function that simulates a single reversal + alternating check, the implementation becomes reasonably simple, and avoids any major casework.
However, to extend this idea to the harder version, looking at the cases closer is actually helpful.
We see that:
- If S contains more than two bad indices, it cannot be made alternating.
- If S is already alternating, there are no issues.
- If S contains exactly one bad index, say x, the above analysis tells us that S can be made alternating if and only if S_1 \neq S_x or S_N \neq S_x.
- If S contains two bad indices, say at x and y, S can be made alternating if and only if S_x \neq S_y.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
def check(l, r):
cur = s[:l] + s[l:r+1][::-1] + s[r+1:]
for i in range(n-1):
if cur[i] == cur[i+1]:
return False
return True
x = 0
while x+1 < n:
if s[x] != s[x+1]: x += 1
else: break
y = x+1
while y+1 < n:
if s[y] != s[y+1]: y += 1
else: break
if x == n-1 or check(0, x) or check(x+1, n-1): print('Yes')
elif y < n-1 and check(x+1, y): print('Yes')
else: print('No')
Tester'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;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
string s; cin >> s;
s = "$" + s;
vector<ll> segs;
rep1(i,n){
if(i > 1 and s[i] != s[i-1]){
segs.back()++;
}
else{
segs.pb(1);
}
}
if(sz(segs) == 1){
yes;
}
else if(sz(segs) == 2){
if(!(segs[0]&1) or !(segs[1]&1)) yes;
else no;
}
else if(sz(segs) == 3){
if(!(segs[1]&1)) yes;
else no;
}
else{
no;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}