Overview

The initial state is RR...RBB...B.
The minimum number of operations to reach the target string \(T\) is the number of adjacent pairs BR in \(T\).

Discussion

First, the operation does not change the count of each color of car.
Therefore, if the number of Rs in \(T\) is not \(A\), it is impossible to reach the target state.

Next, the key observation is to focus on the number of adjacent pairs BR in the string.

For example,

• RRRBBB has \(0\) occurrences of BR
• RBBRBR has \(2\) occurrences of BR
• BRBR has \(2\) occurrences of BR

The initial state RR...RBB...B has no BR.

Here, a single operation can increase the number of BR by at most \(1\).

An operation detaches the last block and inserts it somewhere.
The adjacency relationships that change are only around the detachment point and the insertion point.

While the insertion may create a new BR, at the same time an existing adjacency relationship is destroyed, so as a result, the number of BR increases by at most \(1\) per operation.

Therefore, if the target \(T\) has \(x\) occurrences of BR, at least \(x\) operations are required.

On the other hand, if the number of BR is \(x\), it is actually possible to construct it in \(x\) operations.

For example, if \(T = \texttt{BRBR}\), there are \(2\) occurrences of BR.

If the initial state is RRBB, then:

1. Move the last B to the front
   RRBB → BRRB
2. Move the last B to the middle
   BRRB → BRBR

This achieves the result in \(2\) operations.

In general, if we split \(T\) at the positions of BR, each part has the form R...RB...B.
In other words, by performing as many operations as the number of BR, we can move each B block to the appropriate position to construct \(T\).

Therefore, the answer is the number of BR in \(T\).

If you naively try all operations or search through states, the string length can be up to \(10^7\), which is far too large to handle in time.
All that is needed is to scan the string from left to right and count BR.

Algorithm

1. Count the number of Rs in \(T\).
2. If that count is not \(A\), output -1.
3. Otherwise, examine consecutive characters of \(T\) and count the positions where T[i] == 'B' and T[i+1] == 'R'.
4. Output that count as the answer.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Here, \(N = A + B\).
\(O(N)\) memory is used to store the input string \(T\).

Implementation Notes

Since the length of \(T\) can be up to \(10^7\), we process it with a simple linear scan without using nested loops or the like.

Also, since the length of \(T\) is fixed at \(A+B\), if the number of Rs is \(A\), then the number of Bs is automatically \(B\).

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B;
    string T;
    cin >> A >> B >> T;

    int cntR = 0;
    for (char c : T) {
        if (c == 'R') cntR++;
    }

    if (cntR != A) {
        cout << -1 << '\n';
        return 0;
    }

    int ans = 0;
    for (int i = 0; i + 1 < (int)T.size(); i++) {
        if (T[i] == 'B' && T[i + 1] == 'R') ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.