Reversal ABC (Çözgüdiň düşündirişi)

10pt

Block 1

In this block, the answer can be 0 or 1. To solve it, you need to check whether it is possible to perform at least one operation. If so — output 1, otherwise — 0.

It is necessary to find out if there exists such an $\text{i}$ that the substring s_is_{i+1} equals one of three: AB, BC, or CA.

Block 2

In this block, you need to iterate through all possible strings of length up to 3 and build a branching tree.

Block 3

In this block, the string consists only of characters A and B, so only one operation is possible — on the substring AB.

The final appearance of the string is all B on the left and all A on the right: BB...BBAA...AA, because no other operations can be performed.

To count the number of operations, for each A character, count the number of B characters that follow it and sum it up for all A.

Block 4

For a string of the form AA...AABB...BBCC...CC, let $n$ be the number of A, $m$ be the number of B, and $k$ be the number of C.

It is advantageous either to replace all A and B, or all B and C.

Answer: \max(n \cdot m, m \cdot k).

Block 5

Group identical substrings of characters in the initial string — they will perform operations together.

If the substring CA never occurred, it will not appear after any number of operations.

Proof: if we assume that CA appeared, then before this operation the string had to contain CBA or AC, but none of these strings forms CA.

Only operations on AB and BC are possible. For each B character, consider the following cases:

1. B has A on the left only: interacts with all A until the first C on the left.

2. B has C on the right only: interacts with all C until the first A on the right.

3. B has A on the left and C on the right: choose the maximum of cases 1 and 2.

Block 6

If the string length is $\le 12$, you can run a full recursion.

If no operations can be performed — the answer is 0.

Otherwise, iterate through all possible operations, run recursion for each option, and choose the maximum answer.

Complexity: O(n \cdot 3^n), since the number of states is 3^n, and each state has up to $n$ transitions.

Block 7

To solve this block, precompute the answer for all 3^n states (as in block 6).

After this, each query will be answered in $O(1)$.

Block 9

Group identical substrings of characters in the initial string — they will act together.

The resulting string will look like ...ACBACBACB....

Introduce dp[\text{first symbol}][\text{suffix}] — the answer for the suffix if the first symbol in the result is specified.

Then we search for \max(dp['A'][0], dp['B'][0], dp['C'][0]).

Transitions in $dp$, for example, first\_symbol = \texttt{A} (similarly for others):

- If s[i] = \texttt{A}, then dp[\texttt{A}][i] = \max(dp[\texttt{A}][i+1], dp[\texttt{C}][i+1]) (B cannot follow A). - If s[i] = \texttt{B}, then dp[\texttt{A}][i] = -\infty. - If s[i] = \texttt{C}: - If it is followed by B or the end of the string, then dp[\texttt{A}][i] = -\infty. - If the string looks like CACACACA[C], then move all A to the left:

dp[\texttt{A}][i] = \text{value\_of\_swapping\_all\_A\_to\_left}

- If the string looks like CACACACACB...:

dp[\texttt{A}][i] = \text{value\_of\_swapping\_all\_A\_to\_left} + dp[\texttt{B}][B...]

- If the string looks like CACACACAB..., then:

dp[\texttt{A}][i]= \max(\text{value\_of\_swapping\_all\_A\_to\_left} + dp[\texttt{B}][B...], \text{value\_of\_swapping\_bold\_A\_to\_left} + dp[\texttt{B}][AB...] $)$