Official

F - Beautiful String Editorial by evima

Hints: https://atcoder.jp/contests/agc066/editorial/9708

[0] Note

For simplicity, we assume that the lengths of all strings are at least \(3\).

This editorial omits some details for brevity compared to the author’s other editorials, as rigorous proofs in full detail would be very long.

[1] String representation by differences

Instead of the string \((S_1, \ldots, S_N)\), consider the sequence \((S_1, S_2-S_1, S_3-S_2,\ldots,S_N-S_{N-1})\). Here, subtraction is performed modulo \(3\) by mapping the characters A, B, C to \(0\), \(1\), \(2\), respectively.

In a beautiful string, \(S_{i+1}-S_i \equiv \pm 1\pmod{3}\), so we represent the part \(S_{i+1}-S_i\) as + or -. For example: ABACBCAC becomes A+---++-.

Hereafter, an A+-string is a string whose first character is A, B, or C and the remaining characters are + or -.

By converting the string into an A+-string and reinterpreting the problem’s operations, we find that the possible operations can be classified into the following three types depending on the swap position: the prefix, suffix, or neither.

  • Operation (1)
    • Change +++ to ---.
    • Change --- to +++.
  • Operation (2)
    • Change A++ to B--.
    • Change B++ to C--.
    • Change C++ to A--.
    • Change A-- to C++.
    • Change B-- to A++.
    • Change C-- to B++.
  • Operation (3)
    • For the last two characters, change ++ to --.
    • For the last two characters, change -- to ++.

Note that for strings of length \(2\), there are operations like A+ → B- that do not fit into these types. However, as mentioned at the beginning, this editorial omits such cases.

[2] Considering operation (1) only

We consider when two strings can be transformed into each other by repeating operation (1).

Introduce the following operation:

  • Operation (1’)
    • Delete +++.
    • Delete ---.

Operation (1’) reduces the length of the string, so it can only be performed a finite number of times on the same string. For an A+-string \(S\), let \(f(S)\) denote the string obtained by repeating operation (1’) as much as possible (this is uniquely determined). The following holds:

【Proposition 1】 For two A+-strings \(S_1\) and \(S_2\) of the same length, the following are equivalent.

(a) \(S_1\) and \(S_2\) can be transformed into each other by repeating operation (1).

(b) \(f(S_1)=f(S_2)\) holds.

The proof is omitted, but it is essentially the same as the discussion at the beginning of the official editorial for ABC050B, so refer to it if necessary.

[3] Considering all operations

Let us modify [2] to apply when operations (2) and (3) are also available. Introduce the following operations:

  • Operation (2’)
    • Change A++- to B.
    • Change B++- to C.
    • Change C++- to A.
    • Change A--+ to C.
    • Change B--+ to A.
    • Change C--+ to B.
  • Operation (3’)
    • Delete the last -++.
    • Delete the last +--.

Operation (2’) (resp. (3’)) is the combination of operation (2) (resp. (3)) and operation (1’).

Operations (1’), (2’), (3’) reduce the length of the string, so they can only be performed a finite number of times on the same string. Therefore, for an A+-string \(S\), consider defining \(g(S)\) as the string obtained by repeating operations (1’), (2’), (3’) as much as possible.

The result is generally not unique, so to define the mapping appropriately, we adopt the following definition, which uniquely determines the order of operations.

【Definition】 Define \(g(S)\) as the output of the following algorithm for \(S\).

  1. If operation (1’) can be applied, apply it to the leftmost possible position and return to 1. If not, proceed to 2.
  2. If operation (2’) can be applied, apply it and return to 1. If not, proceed to 3.
  3. If operation (3’) can be applied, apply it and return to 1. If not, output the current \(S\) and end the algorithm.

Then, the following holds.

【Proposition 2】 For two A+-strings \(S_1\) and \(S_2\) of the same length, the following are equivalent.

(a) \(S_1\) and \(S_2\) can be transformed into each other by repeating operations (1), (2), (3).

(b) One of the following holds:

  • (b1) \(g(S_1) = g(S_2)\)
  • (b2-1) Both \(g(S_1)\) and \(g(S_2)\) are either A+ or B-.
  • (b2-2) Both \(g(S_1)\) and \(g(S_2)\) are either B+ or C-.
  • (b2-3) Both \(g(S_1)\) and \(g(S_2)\) are either C+ or A-.
  • (b3) Both \(g(S_1)\) and \(g(S_2)\) are among A++, A--, B++, B--, C++, C--.

Let us briefly describe the proof strategy.

To derive (b) assuming (a), it suffices to show the case where \(S_1\) and \(S_2\) can be transformed into each other by one operation (1), (2), or (3), and the proof can be done by induction. The details are omitted, but it is not difficult.

Consider deriving (a) assuming (b). For simplicity, let us describe the case of (b1). First, operations (1’), (2’), (3’) reduce the length of the string, but alternatively, define operations that supplement +++ at the end after performing operations (1’), (2’), (3’) to keep the string length. Let us show that this operation can be written as a composition of operations (1), (2), (3). 【Proposition 1】 will be useful here.

Next, define \(h(S)\) as the string obtained by adding an appropriate number of + to the end of \(g(S)\) to make it have the same length as \(S\). From the above discussion, it can be seen that \(S\) can be transformed into \(h(S)\) by a composition of operations (1), (2), (3). If \(g(S_1) = g(S_2)\), then \(h(S_1)=h(S_2)\), in which case \(S_1\) and \(S_2\) can be transformed into a common string by a composition of operations (1), (2), (3), so it can be seen that \(S_1\) can be transformed into \(S_2\) by a composition of operations (1), (2), (3).

To show (b2-1), in addition to the above discussion, it suffices to verify that A+-strings obtained by adding + \(3n\) times to the ends of A+ and B- can be transformed into each other by a composition of operations (1), (2), (3). Note that the string length is assumed to be at least \(2\) in this editorial, and consider performing operations (2) and (3) once each and operation (1) \(n-1\) times to show it.

(b3) is similar, so it is omitted.

This concludes the understanding of how two strings can be transformed into each other by the operations in this problem.

By observing these proofs closely, it can be seen that the order of operations in the algorithm defining \(g(S)\) is not important. In fact, if we try to define \(g(S)\) as the result of performing operations (1’), (2’), (3’) in any order, a statement equivalent to 【Proposition 2】 holds, although there remains some indeterminacy such as which of A+ and B- is obtained in the definition of \(g(S)\).

[4] Lexicographical minimization

From 【Proposition 2】, the following problem needs to be solved:

Given an A+-string \(T\), find the lexicographically smallest \(S\) such that \(g(S)=T\).

By tracing operations (1’), (2’), (3’) in reverse, \(S\) can be obtained from \(T\) by repeatedly performing the following:

  • Operation (1”)
    • Add +++.
    • Add ---.
  • Operation (2”)
    • Change A to B--+ or C++-.
    • Change B to C--+ or A++-.
    • Change C to A--+ or B++-.
  • Operation (3”)
    • Add -++ to the end.
    • Add +-- to the end.

For lexicographical minimization, consider creating as long a sequence of ABABAB... as possible at the beginning (in terms of A+-strings, a sequence of A+-+-+-...). Then, if we fix the numbers of operations (2”) and (3”), the optimal way to perform operation (1”) is easily determined.

Basically, increasing the number of operations (2”) and (3”) will shorten the A+-+-... part that can be created, so a straightforward way to implement a solution is to brute-force the numbers of operations (2”) and (3”) within a reasonable range.

The above solves the problem in \(O(|S|)\) time.

posted:
last update: