SWAPSTR - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You’re given a string containing only the characters A,B, and C.
It can be modified as follows:

  • Choose a substring equal to AB and make it BA.
  • Choose a substring equal to BC and make it CB.

Find the maximum possible number of operations you can perform.

EXPLANATION:

Both operations we have involve the character B, so it’s helpful to look at what’s going on from the perspective of the B's in the string.
Of the two operations we have, one functionally moves a B “left” using an A, and the other moves it “right” using a C.
The number of operations performed can thus be thought of as summing up the total number of times each B moves.

So, let’s look at some occurrence of B.
What’s the maximum number of times it can be made to move?

The key observation here is that it’s impossible to make it move both left and right on different moves.
For example, if you make it move left using the move AB \to BA, you’ll never able to do the BC \to CB move on this B in the future, because there’s simply no way to make a C appear to its immediate right.

So, either we perform only leftward movements, or we perform only rightward movements.

Knowing this, let’s define L_i to be the maximum number of leftward movements that the B which is initially at index i can make.

To compute L_i, observe that each leftward movement essentially corresponds to an occurrence of A in the string; since each such movement requires us to “use” an A, and then we can never use it again.
However, while moving left, it’s impossible to cross a C at all.

So, L_i can be computed as follows:

  • Let j \lt i be the largest index such that S_i = C.
  • L_i then equals the number of occurrences of A in the range [j+1, i-1].

One easy way to compute this is to do the following:

  • Maintain the current number of leftward movements, say in variable \text{cur}.
  • Then, for each i from 1 to N:
    • If S_i = A, increase \text{cur} by 1.
    • If S_i = B, assign L_i = \text{cur}.
    • If S_i = C, assign \text{cur} = 0.

Similarly, if we define R_i to be the maximum number of rightward movements the B at index i can make, all the R_i values can be computed in linear time using the same idea (just that the roles of A and C are swapped).

Now that all the L_i and R_i values are known, we have a clear upper bound on the answer: for each index i such that S_i = B, add \max(L_i, R_i) to the answer, i.e. choose to move it either left or right, and take the best option among them.

The only possible concern here is that the L_i and R_i values were computed independently for each i, but adding up \max(L_i, R_i) means there must exist a sequence of operations satisfying all of these constraints simultaneously.
For example, if we run into a case like S = \ldots BB \ldots, and we decide that it’s optimal to move the first B right and the second one left, there’s actually no way to do so since we can’t really swap B's.

Luckily, this turns out to not be an issue: the local optimums we take do in fact lead to the global optimum.

Proof

We start off by ignoring all the B's in the string, to look at the subsequence consisting of only the $$A$'s and C's.
Each move leaves this subsequence unchanged, so it’s an invariant.
The actual string itself is thus defined entirely by the number of B's between each pair of adjacent elements of this AC-subsequence, and each operation just moves a B from one block to another.

So, let’s look at two adjacent characters of the AC-subsequence.
Let the left one be x and the right one be y.
There are four possibilities, we consider each one in turn.

First, consider x = C and y = A.
When this happens, none of the B's between them can move at all.
For all of them, our algorithm will correctly compute 0 as the number of moves, so there’s no issue.

Next, consider x = y = A.
All the B's between these can’t move rightward at all, so L_i will be optimal for each of them.
It’s easy to see that for each B to the left of this block (till the nearest C), the leftward movement will still be the optimal choice since rightward movement will be impossible.
Since they’re all moving left anyway, none of the B's will have their movement be stopped.

x = y = C is similar, but with rightward movement instead.

That leaves x = A and y = C, in which case both leftward and rightward movement are possible.
However, all the B's between them will have the same L_i and R_i values, so they’ll all have the same optimal direction (if L_i = R_i then just choose to move everything left).

In any case, we’re always able to move things in their optimal directions without affecting the movement of any other element, which is exactly what we wanted to do.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    best = [0]*n
    ct = 0
    for i in range(n):
        if s[i] == 'A': ct += 1
        elif s[i] == 'B': best[i] = ct
        else: ct = 0
    ct = 0
    for i in reversed(range(n)):
        if s[i] == 'A': ct = 0
        elif s[i] == 'B': best[i] = max(best[i], ct)
        else: ct += 1
    print(sum(best))
1 Like