Problem Author: | Anton Trygub |
Prepared by: | Roman Pitsura |
Analysis written by: | Roman Pitsura, Igor Barenblat |
10pt
Block 1
In this block, the answer can be 0 or 1. To solve it, you need to check if at least one operation can be performed. If so, output 1; otherwise, output 0.
You need to determine if there exists an such that the substring s_is_{i+1} is equal to one of the 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 the 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 further operations can be performed.
To count the number of operations, for each A, you need to count the number of B that come after it and sum this for all A.
Block 4
For a string of the form AA...AABB...BBCC...CC, let be the number of A, be the number of B, and be the number of C.
It is beneficial to either replace all A and B or all B and C.
The answer is: \max(n \cdot m, m \cdot k).
Block 5
Let's group identical substrings of characters in the initial string — they will perform operations together.
If the substring CA has never appeared, it will not appear after any number of operations.
Proof: If we assume that CA appeared, then before this operation, the string must have contained CBA or AC, but neither of these strings can produce CA.
Only operations on AB and BC are possible. For each B, we consider the following cases:
1. B has only A to the left: it interacts with all A up to the first C on the left.
2. B has only C to the right: it interacts with all C up to the first A on the right.
3. B has A on the left and C on the right: we choose the maximum from cases 1 and 2.
Block 6
If the length of the string is , we can run full recursion.
If operations cannot be performed — the answer is 0.
Otherwise, we iterate through all possible operations, run recursion for each variant, and choose the maximum answer.
Complexity: O(n \cdot 3^n), since the number of states is 3^n, and from each state, there are up to transitions.
Block 7
To solve this block, we first calculate the answer for all 3^n states (as in block 6).
After that, we will answer each query in .
Block 9
Let's group identical substrings of characters in the initial string — they will act together.
The resulting string will look like ...ACBACBACB....
We introduce dp[\text{first symbol}][\text{suffix}] — the answer for the suffix if the first symbol in the result is the specified one.
Then we look for \max(dp['A'][0], dp['B'][0], dp['C'][0]).
Transitions in , 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]) (after A, there cannot be a B). - If s[i] = \texttt{B}, then dp[\texttt{A}][i] = -\infty. - If s[i] = \texttt{C}: - If B follows or it is the end of the string, then dp[\texttt{A}][i] = -\infty. - If the string looks like CACACACA[C], then we 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\_all\_A\_to\_left} + dp[\texttt{B}][AB...]