Let's store the last moment when somebody gets a tea in the variable $$$lst$$$. Then if for the $$$i-th$$$ student $$$lst ≥ ri$$$ then he will not get a tea. Otherwise he will get it during max($$$lst$$$ + 1, $$$l_i$$$) second. And if he gets a tea then $$$lst$$$ will be replaced with the answer for this student.

[submission:159713776]

• Approach 1:
  Let's use STL function std::lower_bound() to solve this problem. First make vector of pair of <Total_Damage,Time_Stamp> and then use the lower_bound() function to find the smallest Total Damage just greater than or equal to $$$c_j$$$ and then print the Time Stamp corresponding to that damage. Reference for lower_bound() function
  Time Complexity: $$$O(n+m\cdot log(n))$$$
  NOTE: This problem could have been solved using binary search but wasn't needed since you know STL.

• Approach 2:
  First sort the $$$c$$$ array using std::sort() function (in $$$O(m\cdot log(m))$$$ time) and then iterate through $$$c$$$. Once you find the smallest damage $$$a_i >= c_j$$$ then you know that that $$$c_{j+1} >= a_i$$$. Use this fact to solve the question in $$$O(n+m)$$$ (after sorting) time.
  Time Complexity: $$$O(n+m\cdot log(m))$$$

[submission:160223611]

Use stacks to maintain the current state. If the top 2 elements of the stack are the same at a particular instant, then remove those two elements. Keep doing this until you find an unequal pair or stack becomes empty.

[submission:159716108]

Let's denote $$$A(l, r)$$$ as some stack-sortable array which contains all integers from $$$l$$$ to $$$r$$$ (inclusive).

We can see that if the first element of $$$A(l, r)$$$ is $$$x$$$, then $$$A(l, r) = [x] + A(l, x - 1) + A(x + 1, r)$$$, where by  +  we mean concatenation of arrays. It's easy to prove this fact: if the first element is x, then we have to store it in the stack until we have processed all elements less than $$$x$$$, so in $$$A(l, r)$$$ no element that is greater than $$$x$$$ can precede any element less than $$$x$$$.

This way we can represent the prefix we are given. For example, if $$$n = 7, k = 3$$$ and prefix is $$$[6, 3, 4]$$$, then we can rewrite the permutation we have to obtain as:

$$$A(1, 7) = [6] + A(1, 5) + A(7, 7) = [6] + [3] + A(1, 2) + A(4, 5) + A(7, 7) = [6] + [3] + [1] + A(2, 2) + A(4, 5) + A(7, 7)$$$

So the unknown suffix is a contatenation of some stack-sortable arrays. It's easy to see that if an array is sorted in non-increasing order, then it is stack-sortable. So we can replace each block $$$A(x, y)$$$ with an array $$$[y, y - 1, y - 2, ..., x]$$$.

If during rewriting the given prefix we obtain some impossible situation (for example, when $$$n = 7$$$ and given prefix is $$$[6, 7]$$$, we have $$$[6] + A(1, 5) + A(7, 7)$$$ and $$$7$$$ can't be the beginning of $$$A(1, 5)$$$), then answer is -1.

#include <bits/stdc++.h>
using namespace std; 
 
int main(){
    int n, k; cin >> n >> k;
    
    int A[n], pt = 1; stack<int> stk;
    for (int i = 0; i < n; i++){
        if (i < k) cin >> A[i];
        else A[i] = stk.empty() ? n : stk.top() - 1;
        stk.push(A[i]);
        while (stk.size() and stk.top() == pt) stk.pop(), pt++; 
    }
    
    if (stk.size()) return cout<<-1, 0;
    for (int i : A) cout<<i<<" ";
}

One can notice (or actually derive using some maths) that the answer is the sum of products of nested for loops iterations for every "add" command.

Let's learn to simulate that in linear complexity. Maintain the stack of multipliers: on "for $$$n$$$" push the top of stack multiplied by $$$n$$$ to the stack, on "end" pop the last value, on "add" add the top of the stack to the answer.

The problem, however, is the values are really large. Notice that once you add the value greater or equal to $$$2^{32}$$$ to the answer, it immediately becomes "OVERFLOW!!!". Thus let's push not the real multiplier to the stack but min(multiplier, $$$2^{32}$$$). That way the maximum value you can achieve is about $$$2^{32}\cdot 50000$$$, which fits into the 64-bit integer.

Overall complexity: $$$O(n)$$$.

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < int(n); i++) 

using namespace std;

const long long INF = 1ll << 32;

int main(){
	int l;
	cin >> l;
	
	stack<long long> cur;
	cur.push(1);
	
	long long res = 0;
	forn(_, l){
		string t;
		cin >> t;
		if (t == "for"){
			int x;
			cin >> x;
			cur.push(min(INF, cur.top() * x));
		}
		else if (t == "end"){
			cur.pop();
		}
		else{
			res += cur.top();
		}
	}
	
	if (res >= INF)
		cout << "OVERFLOW!!!" << endl;
	else
		cout << res << endl;
}

Considerr some segment of consecutive equal characters. Let $$$k$$$ be the length of that segment. Easy to see that we should change at least $$$\lfloor \frac{k}{2} \rfloor$$$ characters in the segment to remove all the pairs of equal consecutive letters. On the other hand we can simply change the second, the fourth etc. symbols to letter that is not equal to the letters before and after the segment.

const int N = 200200;

int n;
char s[N];

bool read() {
	if (!gets(s)) return false;
	n = int(strlen(s));
	return true;
}

void solve() {
	for (int i = 0, j = 0; i < n; i = j) {
		while (j < n && s[j] == s[i]) j++;
		char c = 'a';
		while (c == s[i] || (i > 0 && c == s[i - 1]) || (j < n && c == s[j]))
			c++;
		fore(k, i, j)
			if ((i + k) & 1)
				s[k] = c;
	}
	puts(s);
}

• Approach 1:
  The fractal is built by a recursive function. Let $$$a$$$ be a square $$$n^k × n^k$$$ result matrix. Write the recursive function fractal(x, y, k) filling a square part of the matrix with an upper left corner in $$$(x, y)$$$ and a length of the side $$$n^k$$$, drawing the fractal of depth $$$k$$$. In case $$$k = 0$$$ put . at the current position. Otherwise you have to divide the part of the matrix into $$$n^2$$$ square parts with size $$$n^{k-1} × n^{k-1}$$$, and fill them according to the model. If the corresponding symbol in the model is *, fill the square with symbols *, otherwise execute fractal(x1, y1, k-1) for $$$(x1, y1)$$$ being the coordinates of the upper left corner of the new square.

• Approach 2:
  Consider all positions $$$(x, y)$$$. If for some $$$c = n^d$$$, $$$0 ≤ d < k$$$ the square ((x/c)%n, (y/c)%n) of the model is black then $$$(x, y)$$$ must be black, otherwise it is white. It is easy to check that if the square ((x/c)%n, (y/c)%n) is black for $$$d = k - 1$$$, then we have that the current position $$$(x, y)$$$ is in the black square after the first step of the algorithm. If ((x/c)%n, (y/c)%n) is black for $$$d = k - 2$$$, it happens after the second step, etc.

160379640

Approach 1:

Sort the array using an efficient sorting algorithm. For every element check if the next two in the array are equal to it. If you find such an element output it. Time complexity is $$$O(nlogn)$$$.

Approach 2:

Notice that elements have an upper bound of $$$n$$$, you can use an auxiliary array to store the count of each value. Go through each value and see if its count is bigger than or equal to $$$3$$$. Time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;


int main() {
	int t; cin >> t;
	while(t--) {
	    int n; cin >> n;
    	vector<int> cnt(n + 1, 0);
    	int ans = -1;
    	for(int i = 0; i < n; i++) {
    		int x; cin >> x;
    		if(++cnt[x] >= 3) {
    			ans = x;
    		}
    	}
    	cout << ans << endl;
	}
}

Note that the columns don't affect each other, so we can solve for each column by itself.

For each column, go from the bottom to the top, and keep track of the row of the last obstacle seen; call it last. Note that initially, last$$$=n+1$$$, since we treat the floor as the $$$n+1$$$ th row of obstacles. Whenever we see a new obstacle, we should update last.

Now, if we ever see a stone, we should move it to row $$$last−1$$$, since it will be one row above the last obstacle seen (it will fall on top of it). Afterwards, we should also decrease last by $$$1$$$, because if any future stones fall on top of it, they will land on the row above this stone.

This solution works in $$$O(nm)$$$. We also accepted slower solutions that run in $$$O(n^2m)$$$ that simulate each stone falling.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, m;
	cin >> n >> m;
	char g[n + 7][m + 7];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
		}
	}
	for (int j = 0; j < m; j++) {
		int last = n &mdash; 1;
		for (int i = n &mdash; 1; i >= 0; i--) {
			if (g[i][j] == 'o') {last = i &mdash; 1;}
			else if (g[i][j] == '*') {swap(g[i][j], g[last][j]); last--;}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << g[i][j];
		}
		cout << '\n';
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

Let's call $$$b_i$$$ local minimum if $$$b_i−1>b_i<b_i+1$$$ and local maximum if $$$b_i−1<b_i>b_i+1$$$. It's clear that in the arrangement satisfying the conditions from the statement, if $$$b_i$$$ is a local minimum, $$$b_i+1$$$ is a local maximum, and vice versa. Local minimums and local maximums will be alternating.

Then it's easy to see that such an arrangement can't exist for odd $$$n$$$. Indeed, suppose that the conditions from the statement are satisfied for $$$b_1,b_2,\dots,b_n$$$. If we suppose that $$$b_1$$$ is local minimum, we get that $$$b_2$$$ is local maximum, $$$b_3$$$ is local minimum, …, $$$b_n$$$ is local minimum, $$$b_1$$$ is local maximum. Clearly, $$$b_1$$$ can't be a local maximum and a local minimum at the same time, leading to a contradiction.

Let's now consider the case of even $$$n=2m$$$. Sort the array $$$a$$$, so that $$$a_1≤a_2≤\dots≤a_{2m}$$$. Let's show that if $$$a_i=a_i+m−1=x$$$ for some $$$2≤i≤m−1$$$, then there is no arrangement satisfying the conditions from the statement. Indeed, consider such an arrangement: we have $$$m$$$ numbers $$$x$$$, and no two of them can be adjacent, so they occupy every second position. In addition, as local maximums and local minimums are alternating, we get that all $$$x$$$ are local maximums or all $$$x$$$ are local minimums. The first would imply that $$$a_{2m}<x$$$, which isn't possible. The second would imply that $$$a_1>x$$$, which isn't possible.

It turns out that if there is no such $$$i$$$, the arrangement exists. Indeed, we can arrange numbers on the circle in the following order: ($$$a_1,a_{m+1},a_2,a_{m+2},\dots,a_m,a_{2m}$$$). Here $$$a_k<a_{m+k}>a_k+1$$$ for $$$1≤k≤m−1$$$, $$$a_{m+k}>a_k+1<a_{m+k+1}$$$ for $$$1≤k≤m−1$$$, $$$a_{2m}>a_1<a_{m+1}$$$ and $$$a_m<a_{2m}>a_1$$$.

#include <bits/stdc++.h>
 
using namespace std;
int n, w, t[200005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> w;
    while (w--) {
        cin >> n;
        for (int i=1; i<=n; i++) {
            cin >> t[i];
        }
        sort(t+1, t+n+1);
        int cnt=0, f=n/2;
        for (int i=1; i<=n; i++) {
            if (t[i]==t[f]) cnt++;
        }
        if (n%2 || 2*cnt>=n && t[f]==t[f+1]) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
            for (int i=1; i<=f; i++) {
                cout << t[i] << " " << t[i+f] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

First let's notice that the first player makes $$$\lceil \frac{n-1}{2} \rceil$$$ turns and the second one makes $$$\lfloor \frac{n-1}{2} \rfloor$$$.

So, if numbers are $$$1$$$-indexed and sorted, first player can make the answer not more than $$$\left(n−\lceil \frac{n-1}{2} \rceil\right)$$$-th by deleting maximal number every time. The second can make it not less than $$$\left(\lfloor \frac{n-1}{2} \rfloor+1\right)$$$-th.

But $$$n−\lceil \frac{n-1}{2} \rceil=\lfloor \frac{n-1}{2} \rfloor+1$$$, because $$$n−1=\lceil \frac{n-1}{2} \rceil+\lfloor \frac{n-1}{2} \rfloor$$$.

So the answer has minimal and maximal values, which are the same. So the answer is $$$\left(\lfloor \frac{n-1}{2} \rfloor+1\right)$$$-th number ascending.

Asymptotics is $$$O(n⋅log(n))$$$ or $$$O(n^2)$$$

#include <bits/stdc++.h>
 
using namespace std;
 
int a[1000];
 
int main() {
  int n;
  cin >> n;
 
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
 
  sort(a, a + n);
 
  cout << a[(n - 1) / 2];
}

Read the statement carefully!! The given string is a palindrome.

Let's remove some index $$$i$$$ from the first half of $$$s$$$ and check whether the resulting string is a palindrome or not, the other half has the same approach. The prefix of length $$$i−1$$$ already matches with the suffix of the same length because the initial string was a palindrome, so we just need to check if $$$t=s[i+1\dots n−i+1]$$$ is a palindrome.

For $$$t$$$ to be a palindrome, $$$s_{n−i+1}$$$ should be equal to $$$s_{i+1}$$$ which was initially equal to $$$s_{n−i}$$$, again which should be equal to $$$s_{i+2}$$$ and this goes on. Here we can see that $$$s_i=s_{i+1}\dots=s_{n−i}+1$$$. So the answer is simply equal to the number of contiguous same characters in the center of the string which can be calculated in $$$O(n)$$$.

#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
 
using namespace std;
 
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
 
void solve(){
    ll n,count=1;
    string s;
    cin>>n>>s;
    for(int i=1;i<(n+1)/2;i++){
        if(s[i]!=s[i-1])count=1;
        else count++;
    }
    if(n%2) cout<<2*count-1<<endl;
    else cout<<2*count<<endl;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--) solve();
}

Let the number of buses with two axles is $$$x$$$ and the number of buses with three axles is $$$y$$$. Then the equality $$$4x+6y=n$$$ must be true. If $$$n$$$ is odd, there is no answer, because the left part of the equality is always even. Now we can divide each part of the equality by two: $$$2x+3y=\frac{n}{2}$$$.

Let's maximize the number of buses. Then we should make $$$x$$$ as large as possible. So, we will get $$$2+\dots+2+2=\frac{n}{2}$$$ if $$$\frac{n}{2}$$$ is even, and $$$2+\dots+2+3=\frac{n}{2}$$$ otherwise. In both cases the number of buses is $$$\lfloor \frac{n}{2} \rfloor$$$.

Now let's minimize the number of buses. So, we should make $$$y$$$ as large is possible. We will get $$$3+\dots+3+3+3=\frac{n}{2}$$$ if $$$\frac{n}{2}$$$ is divisible by $$$3,3+\dots+3+3+2=\frac{n}{2}$$$ if $$$n≡2$$$ (mod $$$3$$$), and $$$3+\dots+3+2+2=\frac{n}{2}$$$ if $$$n≡1$$$ (mod $$$3$$$). In all cases the number of buses is $$$\lceil \frac{n}{3} \rceil$$$.

Also don't forget the case $$$n=2$$$ — each bus has at least four wheels, so in this case there is no answer.

Time complexity: $$$O(1)$$$.

#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
 
using namespace std;
 
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
 
void solve(){
    ll n;
    cin>>n;
    if(n<4 || n%2==1){
        cout<<"-1"<<endl;
        return;
    }
    if(n%6==0) cout<<n/6<<" ";
    else cout<<n/6+1<<" ";
    cout<<n/4<<endl;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--) solve();
}

Imagine that all elements of $$$a$$$ are distinct. This way, sorting $$$a$$$ in increasing order will fix the order of $$$b$$$.

If $$$b$$$ turns out sorted in a non-decreasing order, then the answer exists. Otherwise, it doesn't. To obtain the sequence of swaps, you can sort $$$a$$$ with any comparison-based sorting algorithm you want: even bubble sort will not exceed the allowed number of swaps.

What changes if $$$a$$$ has repeated elements? Distinct elements are still ordered among themselves, but now there are also blocks of equal elements. For each block, look into the corresponding values in $$$b$$$. Obviously, these have to be sorted in a non-decreasing order. Rearrange them as they should be.

In fact, this is exactly the same as sorting the sequence of pairs $$$(a_i,b_i)$$$ with a default comparator — first by $$$a_i$$$, then by $$$b_i$$$.

Since we fixed the wanted order, we can proceed with the same steps we made in a distinct case.

Overall complexity: $$$O(n\cdot log(n))$$$ or $$$O(n^2)$$$ per testcase.

#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
 
using namespace std;
 
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
 
void solve(){
    ll n,count=0;
    vector<pair<int,int> >v;
    cin>>n;
    vector<ll> a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j]){
                if(b[i]<b[j]){
                    cout<<"-1"<<endl;
                    return;
                }else{
                    count++;
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    v.push_back(make_pair(i,j));
                }
            }else if(a[i]<a[j]){
                if(b[i]>b[j]){
                    cout<<"-1"<<endl;
                    return;
                }
            }else{
                if(b[i]>b[j]){
                    count++;
                    swap(b[i],b[j]);
                    v.push_back(make_pair(i,j));
                }
            }
        }
    }
    cout<<count<<endl;
    for(int i=0;i<v.size();i++) cout<<v[i].first+1<<" "<<v[i].second+1<<endl;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--) solve();
}

The solution is to check the sum over all diagonals for each cell.

For a cell $$$(i,j)$$$ we can iterate over all elements in all its diagonals. This will be in total $$$O(max(n,m))$$$ elements.

The complexity will be $$$O(n\cdot m\cdot max(n,m))$$$.

$$$O(n\cdot m)$$$ solutions involving precomputation are also possible but aren't needed.

#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
 
using namespace std;
 
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
 
void solve(){
    ll n,m,ans=0;
    cin>>n>>m;
    vector<ll> k(m),a(n+m-1,0),b(n+m-1,0);
    vector<vector<ll> > v(n,k);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
            if(j>=i) a[j-i]+=v[i][j];
            else a[m-1+i-j]+=v[i][j];
            b[i+j]+=v[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ll k=b[i+j]-v[i][j];
            if(j>=i) k+=a[j-i];
            else k+=a[m-1+i-j];
            ans=max(k,ans);
        }
    }
    cout<<ans<<endl;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--) solve();
}

At first, let's check wether the given table is good. If it is not then there is a row that has elements that should be replaced.

Let's say that this row is $$$a$$$ and $$$b$$$ is the sorted row $$$a$$$. Then let's find the set of positions $$$i$$$ that $$$a_i\neq b_i$$$. If there are at least $$$3$$$ such positions then the answer is $$$−1$$$ because by making a swap we remove at most $$$2$$$ such bad positions. If there are no more than $$$2$$$ such positions then let's swap the corresponding columns and check whether each row is sorted. If the table is good we found the answer. If it is not then the answer is $$$−1$$$ because we can not sort $$$a$$$ and get a good table after that.

#include <bits/stdc++.h>

using namespace std;

void solve(vector<vector<int>> &a) {
    int n = a.size(), m = a[0].size();
    vector<int> bad;
    for (int i = 0; i < n && bad.empty(); i++) {
        vector<int> b = a[i];
        sort(b.begin(), b.end());
        for (int j = 0; j < m; j++) {
            if (a[i][j] != b[j]) bad.push_back(j);
        }
    }
    if ((int)bad.size() == 0) {
    	cout << 1 << " " << 1 << "\n";
    	return;
    }
    if ((int)bad.size() > 2) {
    	cout << -1 << "\n";
    	return;
    }
    for (int i = 0; i < n; i++) {
        swap(a[i][bad[0]], a[i][bad[1]]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (a[i][j] < a[i][j - 1]) {
            	cout << -1 << "\n";
            	return;
           	}
        }
    }
    cout << bad[0] + 1 << " " << bad[1] + 1 << "\n";
    return;
}

int main() {
	#ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> a(n, vector<int>(m));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> a[i][j];
			}
		}
		solve(a);
	}
	return 0;
}

First note that parts of the picture separated by $$$\texttt{W}$$$ are independent. That is, any stamps used on one part doesn't have any impact on the other, since a character $$$\texttt{W}$$$ means no stamp has been placed on that cell. So let's split the string by $$$\texttt{W}$$$ s (for example, with $$$\texttt{split()}$$$ method in Python), and consider the resulting strings containing only $$$\texttt{R}$$$ and $$$\texttt{B}$$$. Call one of these parts $$$p$$$.

In the final stamp we place on $$$p$$$, we must have placed $$$\texttt{RB}$$$, so it should have both the characters $$$\texttt{R}$$$ and $$$\texttt{B}$$$. Therefore, if the string has only $$$\texttt{R}$$$ or only $$$\texttt{B}$$$, the answer is $$$\texttt{NO}$$$.

Otherwise, the answer is $$$\texttt{YES}$$$. Let's show it. As we have just shown, we must have $$$\texttt{R}$$$ next to $$$\texttt{B}$$$ for the string to be possible. Consider the way to make $$$\texttt{RBRRBBBB}$$$. The final stamp can be $$$\texttt{RBR$$$\underline{\texttt{RB}}$$$BBB}$$$. For the rest of the cells, we can make them one by one as below.

$$$\texttt{WWWWWWWW} \rightarrow \texttt{$$$\underline{\texttt{RB}}$$$WWWWWW} \rightarrow \texttt{R$$$\underline{\texttt{BR}}$$$WWWWW} \rightarrow \texttt{RB$$$\underline{\texttt{RB}}$$$WWWW} $$$,

so now we have made the prefix of the string before the final stamp. Similarly:

$$$\texttt{RBRBWWWW} \rightarrow \texttt{RBRBWW$$$\underline{\texttt{RB}}$$$} \rightarrow \texttt{RBRBW$$$\underline{\texttt{RB}}$$$B} \rightarrow \texttt{RBRB$$$\underline{\texttt{RB}}$$$BB}$$$.

Now we have made the prefix and the suffix by stamping "one character" at a time (actually, we stamp two characters, but then cover it up with another stamp).

Finally, we can put the final stamp to make the whole string.

$$$\texttt{RBRBRBBB} \rightarrow \texttt{RBR$$$\underline{\texttt{RB}}$$$BBB}$$$.

This method easily generalizes to any string. We can find the final stamp and then make the prefix and suffix one by one. The solution runs in $$$O(n)$$$.

#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
 
using namespace std;
 
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
 
void solve(){
    ll n,a=0,b=0;
    string s;
    cin>>n>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='R') a++;
        else if(s[i]=='B') b++;
        else{
            if((!a && b)||(!b && a)){
                cout<<"NO"<<endl;
                return;
            }
            a=0;
            b=0;
        }
    }
    if((!a && b)||(!b && a)){
        cout<<"NO"<<endl;
        return;
    }
    cout<<"YES"<<endl;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--) solve();
}