Let us classify the elements of \(B\) into three types:

• ones that are added to the beginning of \(B\) (type-L),
• ones that are originally in \(B\) and not moved (type-M) and
• ones that are added to the end of \(B\) (type-R).

It is obvious that the sequence \(B\) can be divided into three segments as LLL…LLMMM…MMRRR…RR. There exist \(O(N^2)\) possibilities of where to divide the sequence. In the sequel of the argument we assume that a division is fixed.

For each of type-M elements, let us think about where it was originally in \(A\).

For each \(x\), observe to which of L, M and R three copies of \(x\) are classified. For example, if they are classified to L, M and M in this order, out of three copies of \(x\) the first and the third correspond to the two type-M elements in \(B\). This is illustrated below.

A: ... x ... x ... x ...
        \          |
          \        |
            \      |
B: ... L ... M ... M ...

Let us write this as:

M*M
LMM

By case analysis and a similar argument, in most cases the correspondence is determined uniquely. Concretely, the exhaustive list is below.

M** ***
LMR LLR  these two are called (1)

**M ***
LMR LRR  these two are called (2)

M** **M
MRR LLM

MMM
MMM

M*M M*M
LMM MMR

Simply put, if the B-side one is not “LMR”, the correspondence is uniquely determined.

Let us now move on to checking the final sequence \(B\) is realizable for a given correspondence of all type-M elements.

There are two trivial conditions to hold if \(B\) is realizable:

Condition 1 (trivial): matchings do not intersect. Specifically, if two correspondence \( (a_i \to b_j)\) and \((a_k \to b_l)\) of type M exist, \(i < k\) and \(j > l\) don’t hold simultaneously.

Condition 2 (trivial): there do not exist correspondences that are not mentioned above.

Besides, there is another nontrivial condition:

Condition 3: let X denote the leftmost and the rightmost element in the correspondences of type (1), and let Y denote the leftmost and the rightmost element in the correspondences of type (2). \(B\) does not look like the following:

YX ... YX

It turns out that the conjunction of Condition 1, 2 and 3 is equivalent to \(B\)’s realizability. Sufficiency can be proved by explicitly constructing a sequence of operations by e.g. topological sorting.

Furthermore, if \(B\) is realizable there exists a sequence of operations that touches all elements that are not type-M exactly once. This evidently achieves the minimum possible number of operations.

Therefore, we see that once we know a correspondence we can solve this problem. However, in general correspondences are not determined uniquely, so there is some food fort thought.

Why correspondences are not determined uniquely is we cannot tell which one of the following two correspondences is correct when an LMR happens:

M** **M
LMR LMR

However, if we introduce boolean variables that represent which one of these two correspondences to choose, it turns out that Conditions 1 and 3 can be encoded as 2-\({\rm {\small SAT}}\) clauses.

The problem can be solved in \(O(N^4)\) time, trying \(O(N^2)\) segment divisions each taking \(O(N^2)\) time in 2-\({\rm {\small SAT}}\).