PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given a string that contains only the characters R and G.
Is it possible to reverse at most one substring and end up with a string that doesn’t have K consecutive equal characters?
EXPLANATION:
We’ll call a substring whose characters are all the same, a run.
Our aim is to not have any run with length \geq K.
First, if S initially has no runs with length \geq K, the answer is of course immediately Yes; so we only need to care about the case when long runs do exist.
Suppose [l, r] is a run of length \geq K.
Now, if we choose to reverse substring [L, R],
- If L \gt r or R \lt l, then [l, r] is unchanged and will still be a long run; bad for us.
- If L \leq l and r \leq R (so the run is fully contained inside what we reverse), the run will still be present in the string, just at a different position.
This is also bad for us.
So, the only viable options are to have l \leq L \leq r \lt R or L \lt l \leq R \leq r, i.e. to “cut” the long run somewhere in the middle using our operation.
Since we can only perform one operation, we have only two endpoints: meaning we can only “cut” at most two runs.
So, if the string contains three or more long runs, the answer is immediately No.
Further, if there’s a run with length \geq 2K-1, no matter how we cut it one part with have length \geq K, meaning it’s again impossible to attain our goal. The answer is again No in this case.
This leaves us with the case where there are \leq 2 long runs, and they both have length \leq 2K-2.
First, let’s look at the case where there are two separate long runs.
Here, we’re forced to cut both runs with our operation: one endpoint for each run.
There are two possible cases here: the runs can be of the same ‘type’ (as in, both are of the form GGG\ldots or BBB\ldots), or one of them can be GGG\ldots and the other can be BBB\ldots
If both are the same type, it’s not hard to see that no solution exists.
This is because cutting both runs with the reversal operation will result in their lengths basically being redistributed (since . However, since both lengths are initially \geq K, no matter how the redistribution is done at least one part will have length \geq K.
On the other hand, if both runs are of different types, then a solution always exists: simply split both runs in half and reverse, for example.
This works because we’ve ensured that both runs have length \leq 2K-2 now, so after the split everything will be \leq K-1.
Now, we have to deal with the case where there’s only one long run.
Suppose this run is [l, r], and let C = r-l+1 be its length.
As noted above, our options now are l \leq L \leq r \lt R or L \lt l \leq R \leq r.
Let’s look at the first one for now: the other case is symmetric.
Suppose we fix R \gt r, and want to figure out if a valid L exists.
Note that this is equivalent to splitting the run of length C into two parts of lengths x and C-x; so we’ll instead focus on checking validity of x.
For a split length x to be valid, the following conditions must hold:
- If S_R = S_l, then after the reversal, the x part of the split will merge with the substring ending at R.
So, if \text{end}_R is the length of the run ending at R, we must have x+\text{end}_R \lt K.
This means x \lt K - \text{end}_R. - If S_l = S_{R+1}, then the C-x part of the split will merge with the substring starting at R+1.
So, if \text{start}_{R+1} is the length of the run starting at R+1, we want C-x + \text{start}_{R+1} \lt K.
This means C+\text{start}_{R+1} - K \lt x.
We now have both upper bounds and lower bounds on x.
If there are valid bounds - that is, they don’t conflict, and there does exist an integer in
[K - \text{end}_R + 1, C + \text{start}_{R+1} - K - 1],
then we have a valid x and we’re done; otherwise no valid x exists for this R.
Observe that if we know the values of \text{start}_{R+1} and \text{end}_R, this check can be done in constant time for a fixed R, for \mathcal{O}(N) overall.
Computing the \text{start} and \text{end} arrays is quite easy once [l, r] is known, of course:
- \text{end}_i = 0 if S_i \neq S_l
- \text{end}_i = \text{end}_{i-1} + 1 otherwise.
- \text{start}_i is similar but with i+1 instead of i-1.
This solves the problem in linear time.
For ease of implementation, the other case (of L \lt l and l \leq R \leq r) can be solved by just running the above algorithm on the reverse of S.
This avoids having to do any unnecessary copy-paste work which makes the code long and hard to debug.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k; cin >> n >> k;
string s; cin >> s;
// if some run >= K, need to reverse to lessen it
vector <int> a;
for (int i = 0; i < n; i++){
int j = i;
while (j + 1 < n && s[j + 1] == s[i]){
j++;
}
a.push_back(j - i + 1);
i = j;
}
vector <int> bad;
for (int i = 0; i < a.size(); i++){
if (a[i] >= k){
bad.push_back(i);
}
if (a[i] >= 2 * k - 1){
cout << "NO\n";
return;
}
}
if (bad.size() >= 3){
cout << "NO\n";
return;
}
if (bad.size() == 2){
if (bad[0] % 2 != bad[1] % 2){
cout << "YES\n";
} else {
cout << "NO\n";
}
return;
}
if (bad.size() == 0){
cout << "YES\n";
return;
}
if ((bad[0] % 2) == 1){
cout << "YES\n";
return;
}
if ((bad[0] % 2) == (a.size() % 2)){
cout << "YES\n";
return;
}
for (int i = 0; i < a.size(); i++){
if (i % 2 != bad[0] % 2){
if (a[i] > 1){
cout << "YES\n";
return;
}
} else {
// a[i] + a[bad[0]] must be distibutable
if (a[i] + a[bad[0]] <= 2 * k - 2){
cout << "YES\n";
return;
}
}
}
cout << "NO\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
def solve(s, k):
n = len(s)
cur, runs, who = 0, [], s[0]
big = 0
for c in s:
if c == who: cur += 1
else:
runs.append(cur)
big += cur >= k
cur = 1
who = c
runs.append(cur)
big += cur >= k
if max(runs) < k: return 1
if max(runs) >= 2*k - 1: return 0
if big > 2: return 0
if big == 2:
for i in range(len(runs)):
if runs[i] < k: continue
for j in range(i+1, len(runs)):
if runs[j] < k: continue
return i%2 != j%2
# one bad run
lt = max(runs)
st, en = [0]*(n+1), [0]*(n+1)
L, R = 0, 0
for x in runs:
R = L+x-1
if x >= k: break
L += x
for i in range(R+1, n):
if s[i] != s[L]: en[i] = 0
else: en[i] = en[i-1] + 1
for i in reversed(range(R+1, n)):
if s[i] != s[L]: st[i] = 0
else: st[i] = 1 + st[i+1]
for i in range(R+1, n):
# x + en[i] < k => x < k - en[i]
hi = k - en[i] - 1
# lt - x + st[i+1] < k => x > lt + st[i+1] - k
lo = lt + st[i+1] - k + 1
if lo <= hi: return 1
return 0
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
if solve(s, k) or solve(s[::-1], k): print('Yes')
else: print('No')
Author's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
using namespace std;
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() && !isspace(buffer[now])) {
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 readInts(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();
}
return v;
}
auto readLongs(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();
}
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);
}
}inp;
int smn = 0;
void solve()
{
int n,k;
// cin >> n >> k;
n = inp.readInt(1,200'000);inp.readSpace();
k = inp.readInt(2,n+1);inp.readEoln();
string s;
// cin >> s;
s = inp.readString(n,n,"BG");inp.readEoln();
smn += n;
for(auto &x : s){
if(x == 'B')x = '1';
else x = '0';
}
vector<int> v[2];
int ct = 1;
int f = s[0]-'0';
for(int i = 1;i < s.size();i++){
if(s[i] == s[i-1])ct++;
else{
v[f].push_back(ct);
f ^= 1;
ct = 1;
}
}
v[f].push_back(ct);
if(ct == n && ct >= k){
cout << "NO\n";
return;
}
if(ct == n){
cout << "YES\n";
return;
}
sort(v[0].begin(),v[0].end());
sort(v[1].begin(),v[1].end());
if(max(v[0].back(),v[1].back()) >= 2*k-1){
cout << "NO\n";
return;
}
if(v[0].size() > 1 && v[0][v[0].size()-2] >= k){
cout << "NO\n";
return;
}
if(v[1].size() > 1 && v[1][v[1].size()-2] >= k){
cout << "NO\n";
return;
}
if(v[0].back() < k && v[1].back() < k){
cout << "YES\n";
return;
}
if(v[0].back() >= k && v[1].back() >= k){
cout << "YES\n";
return;
}
if(v[0].back() < v[1].back()){
swap(v[0],v[1]);
for(auto &x : s){
if(x == '0')x = '1';
else x = '0';
}
}
if(s.front() == '1' || s.back() == '1' || v[1].back() > 1){
cout << "YES\n";
return;
}
if(v[0].front()+v[0].back() < 2*k-1){
cout << "YES\n";
}
else{
cout << "NO\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
// cin >> t;
t = inp.readInt(1,100'000);
inp.readEoln();
while(t--)
solve();
assert(smn <= 200'000);
inp.readEof();
}