The possible operations are three types of length-\(2\) operations (BA → AB / CA → AC / CB → BC) and the following three types of length-\(3\) operations.

• BCA → ABC
• CAB → ABC
• CBA → ABC

For reachability, it suffices to consider only the length-\(2\) operations. The essence of this problem is how the introduction of the length-\(3\) operations affects the number of operations.

First, note that every length-\(3\) operation swaps exactly one CA pair. Hence, the total number of length-\(3\) operations plus CA → AC operations is always constant. In other words, we can regard this problem as one where BA → AB and CB → BC cost \(1\), and all other operations cost \(0\).

Next, for each B, consider “the number of As to its right” and “the number of Cs to its left.” This lets us regard the Bs as \(N\) pieces moving on two-dimensional lattice points.

From this viewpoint, the problem can be seen as something like a multi-commodity flow problem on a \(2\)-dimensional plane.

Basically, each unit of movement of a B costs \(1\). However, at each lattice point (= CA pair), at most one B movement can be carried along for free.

Since the graph is planar, flow paths can be exchanged whenever they cross. Therefore, all the conditions can ultimately be written as a single-commodity flow, that is, a minimum-cost flow.

In more detail, we map a string containing \(N\) each of A / B / C to a Young diagram on two-dimensional lattice points and pieces on its boundary, by the following procedure.

• Start from \((N, 0)\) and read the characters of the string from the beginning.
• When an A appears, decrease \(x\) by \(1\); when a C appears, increase \(y\) by \(1\).
• When a B appears, place one piece at the current point (multiple pieces may be placed at the same point).

In this way, \(S\) corresponds to a Young diagram with pieces, and the task becomes transforming it by operations into the Young diagram with pieces corresponding to \(T\).

By examining how the polyline and the pieces change under each operation, we can see that the solution given by the flow above is achievable by repeating the following: “Among the parts of the polyline that need to be flipped, take the one with the largest \((x + y)\). Perform BA → AB / CB → BC if necessary, and then perform an operation that swaps that CA.”

For the complexity, we send a flow of \(O(N)\) through a graph with \(O(N^2)\) vertices and \(O(N^2)\) edges, which takes \(O(N^3 \log N)\) time.

Writer’s solution