Let’s observe how walks change things

First, let’s observe how a single walk changes the string of Xs and Ys representing the directions of Type-C roads.

For example, in the state XXXYXYYXXXYXXXXYYXXY, if we start walking from the first intersection and continue to the last, it will look like the following diagram.

As you can see, the first character becomes Y, and the rest of the characters are shifted one position to the right.

Let’s think about why this happens. Observing the path, we only pass through the roads corresponding to the first character of blocks like XX...X or YY...Y. In other words, XX...X changes to YX...X, and YY...Y changes to XY...Y. This means each block is shifted one character to the right.

---

Turning it into a string problem

In reality, you can start walking from an intermediate intersection and finish at another intermediate intersection. Here is an example of this case.

Even in this case, the essence is the same. Only the substring of the section you passed through “shifts one character to the right.”

Therefore, one walk changes the string in the form of “inserting one X or Y character and then deleting one character from behind it.” Thus, this problem can be rephrased as the following string problem.

Problem Given two strings \(s, t\) of length \(N\), find the minimum number of operations to change \(s\) into \(t\).

• Operation: Insert one X or Y character at any position in the string, and then delete one character from behind it.

This problem would be worth around 600-700 points on AtCoder. In competitive programming, it is sometimes important to reinterpret the problem in the easiest possible way to think about.

---

And then to Dynamic Programming

The new problem is similar to finding the edit distance, and can be solved with a similar dynamic programming (DP) algorithm.

As an example, let’s use \(s = XYXYX\) and \(t = XXYYY\). First, to make it easier to visualize the series of operations to change \(s\) into \(t\), let’s align \(s\) and \(t\) vertically as shown below.

The case on the left can be realized by “performing insertion ① and deletion ❶” → “performing insertion ② and deletion ❷”, but the operations shown on the right are impossible. This is because the deletion position must be to the right of the insertion position. Generalizing, the feasible condition is as follows.

Condition If the numbers of insertions and deletions are counted from left to right, the number of insertions never falls below the number of deletions.

Reason If there is some \(t\) such that “the number of insertions falls below the number of deletions by the \(t\)-th column,” then some operation must be “deleting a character at the \(t\)-th or earlier column and insert a character at the \((t+1)\)-th or later column.” On the other hand, if there is no such \(t\), the operations can be performed from front to back like (①, ❶) → (②, ❷), ensuring that the deletion position is always to the right of the insertion position.

The new problem is to find the minimum number of columns needed for a feasible arrangement. Here, consider filling in the table from left to right, and perform DP to calculate the following values.

• \(dp[i][j]\): What is the minimum number of columns filled when we have written up to the \(i\)-th character of \(s\) and up to the \(j\)-th character of \(t\)?
• However, since \(i \leq j\) must always be satisfied for feasibility, only calculate \(dp[i][j]\) that satisfies \(i \leq j\).

This can be calculated in ascending order of \((i, j)\) according to the following formula.

\[ dp[i][j] = \begin{cases} dp[i-1][j] + 1 & (i \geq 1) \ \cdots \ \text{Case of writing only the first row in the last column (deletion case)} \\ dp[i][j-1] + 1 & (j \geq 1) \ \cdots \ \text{Case of writing only the second row in the last column (insertion case)} \\ dp[i-1][j-1] + 1 & (i \geq 1, j \geq 1, s_i = t_j) \ \cdots \ \text{Case of writing both the first and second rows in the last column} \\ \end{cases} \]

Therefore, the minimum number of operations can be calculated in \(O(N^2)\) time complexity.

---

Finally, reconstruct the answer

In the DP, we found the minimum number of operations, but we can also find the optimal way to construct the table.

There are various ways to reconstruct the actual walks, but here is one easy way.

Suppose it is optimal to delete the \(p_1, p_2, \dots, p_X \ (p_1 < p_2 < \dots < p_X)\) characters of \(s\) and insert the \(q_1, q_2, \dots, q_X \ (q_1 < q_2 < \dots < q_X)\) characters of \(t\). In this case, performing operations from front to back like (①, ❶) → (②, ❷), you will change \(s\) into \(t\) as follows.

• In the order of \(i = 1, 2, \dots, X\), do the following.
  • Delete the \(p_i\)-th character of the current string (the character is \(s_{p_i}\)) and insert the character \(t_{q_i}\) before the \(q_i\)-th character.

In the previous example, the \(3\)-rd and \(5\)-th characters of \(s\) are deleted, and the \(2\)-nd and \(4\)-th characters of \(t\) are the characters inserted. The following diagram shows that the operations are actually as described above.

The original problem was to find how to perform walks, so if you convert each string operation into a walk, you’re done.

How to Convert Operations into Walking

Deleting the \(x\)-th character \(s_x\) and inserting a character \(t_y\) before the \(y\)-th character \((x \geq y)\) corresponds to the following walking.

• Starting point: intersection \(2y\) if \(t_y\) is X, and intersection \(2y-1\) if it is Y
• Ending point: intersection \(2x\) if \(s_x\) is X, and intersection \(2x-1\) if it is Y

---

Sample Solution

A sample implementation in C++ is available at https://atcoder.jp/contests/arc172/submissions/50323432.

In Python, the solution can be implemented as follows. Submitting in Python (PyPy 3.10-v7.3.12) will solve the problem within the time limit.

# Receive input
n = int(input())
s = input()
t = input()

# Dynamic programming
INF = 1012345678
dp = [[INF] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(0, n+1):
	for j in range(i, n+1):
		if i >= 1:
			dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
		if j >= 1:
			dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
		if i >= 1 and j >= 1 and s[i-1] == t[j-1]:
			dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1)

# Reconstructing the answer (x is the number of operations, p is the position of characters to delete in s, q is the position of characters to insert in t)
x = dp[n][n] - n
sidx, p = n, []
tidx, q = n, []
while sidx != 0 or tidx != 0:
	if sidx >= 1 and dp[sidx][tidx] == dp[sidx-1][tidx] + 1:
		sidx -= 1
		p.append(sidx)
	elif tidx >= 1 and dp[sidx][tidx] == dp[sidx][tidx-1] + 1:
		tidx -= 1
		q.append(tidx)
	else:
		sidx -= 1
		tidx -= 1
p, q = p[::-1], q[::-1]

# Output the answer
print(x)
for i in range(x):
	a = q[i] * 2 + (2 if t[q[i]] == 'X' else 1) # Starting intersection
	b = p[i] * 2 + (2 if s[p[i]] == 'X' else 1) # Ending intersection
	print(a, b)