PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given a binary string S of length N.
Treating S as circular, define f(S) to be a binary string of length N with the following rule:
- f(S)_i equals the median of S_{i-1}, S_i, S_{i+1}.
Consider an infinite sequence of strings A, with:
- A_0 = S
- A_i = f(A_{i-1}) for i \ge 1
Find the smallest index i such that A_i = A_{i-1}, or decide that no such i exists.
EXPLANATION:
A_i = A_{i-1} happens if and only if A_{i-1} = f(A_{i-1}), so we first need to understand when a string S can have S = f(S).
Let’s look at a certain index i in S.
Then, if S_i equals either S_{i-1} or S_{i+1} (or both), the median of \{S_{i-1}, S_i, S_{i+1}\} will equal S_i itself since the character S_i has (at least) two occurrences out of three.
So, if S_i equals at least one of its neighbors, we’ll have S_i = f(S)_i.
On the other hand, if S_i is different from both of its neighbors, then clearly S_i \ne f(S)_i.
So, S = f(S) can hold if and only if for every index i, S_i equals at least one of its neighbors.
Let’s call an index i “good” if S_i equals one of its neighbors, and “bad” otherwise.
From what we saw above, the string f(S) can be obtained by taking S and flipping the character at every bad index.
Our desired final state is one where every index is good.
Observe that if an index i is good in S, then it will remain good in f(S) as well.
(This is because S_i equals a neighbor; and so that neighbor is also good - and so both values don’t change in f(S), and will continue to remain good forever).
Thus, it’s enough to care about only the first time that each index becomes good, since it will remain good after that.
Now,
- If a bad index is adjacent to two bad indices, it will remain bad in f(S) (since it will flip but its neighbors will also flip.)
- If a bad index is adjacent to at least one good index, it will become good in f(S) because the neighbor won’t flip.
This tells us that the good indices will “spread out” one step at a time.
For example, if we have S = 101101010,
- Initially, only 3, 4 are good.
- f(S) = 011110101 so 2, 3, 4, 5 are good.
- f(f(S)) = 111111010 so 1, 2, 3, 4, 5, 6 are good.
- f(f(f(S))) = 111111101 so 1, 2, 3, 4, 5, 6, 7, 9 are good.
- Applying the operation once more makes the string all 1’s, and everything becomes good.
Because this happens only one step at a time, and we care about the first time each index becomes good, we have the following result:
- For an index i, the first time it will become good is given by the smallest possible value of \text{dist}(i, j) across all good indices j in S.
- Here, \text{dist}(i, j) denotes the circular distance between i and j.
- This can be calculated as \min(|i-j|, N-|i-j|).
So, our task is simply to find the minimum (circular) distance from each index to an existing good index, and then report the largest of all these distances plus one as the answer.
In particular, if there are no good indices initially, the answer is -1, since in every operation every character will flip and no index can become good.
All that remains is finding the nearest good index to each index of the string.
One way of implementing this is as follows.
Suppose the initially good indices are x_1 \lt x_2 \lt\ldots \lt x_k.
Then, for any index i, it will lie in some interval of the form [x_j, x_{j+1}-1] (here we also treat [x_k, x_1-1] as an interval, since the string is cyclic).
Once this interval is known, we only need to find its distance to x_j and to x_{j+1} and take the minimum among them - that’s the answer.
An alternate solution is to work with “blocks” of bad elements.
Note that each block will have exactly its left and right ends become good in each step - so the block’s length will shrink by 2 each step.
So, a block of length L will take \text{ceil}(\frac{L}{2}) steps for all its elements to become good.
This allows for a solution where we simply find all maximal blocks of bad elements, take the largest length among them, and then the answer is simply half the length of this block rounded up.
This solution is the one implemented below - it first finds all blocks of equal elements in the string, then computes distances between blocks of size \gt 1 (since these are exactly what the good indices are.)
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
vector<int> blocks;
for (int i = 0; i < n; ) {
int j = i;
while (j < n and s[i] == s[j]) ++j;
blocks.push_back(j - i);
i = j;
}
if (s[0] == s.back() and size(blocks) > 1) {
// merge first and last blocks if equal elements, because the string is cyclic
blocks[0] += blocks.back();
blocks.pop_back();
}
for (int i = 0; i < size(blocks); ++i) {
if (blocks[i] > 1) {
// start with a good element, if possible
rotate(begin(blocks), begin(blocks)+i, end(blocks));
break;
}
}
if (blocks[0] == 1) {
cout << -1 << '\n';
continue;
}
blocks.push_back(blocks[0]);
int p = 0, ans = 0;
for (int i = 1; i < size(blocks); ++i) {
if (blocks[i] > 1) {
// everything from prv to i-1 is a size-1 block, hence bad element
ans = max(ans, (i - p)/2);
p = i;
}
}
cout << ans+1 << '\n';
}
}