CCC '24 S3 - Swipe

Canadian Computing Competition: 2024 Stage 1, Senior #3

Swipe is a new mobile game that has recently exploded in popularity. In each level of Swipe, you are given $2$ rows of integers that can be represented as arrays $A$ and $B$ of size $N$. The objective of Swipe is to beat each level by turning array $A$ into array $B$.

There are two swipe operations you can perform on array $A$.

• Swipe right: Select the subarray $[\ell, r]$ and set $A_i = A_\ell$ for all $\ell \le i \le r$.
• Swipe left: Select the subarray $[\ell, r]$ and set $A_i = A_r$ for all $\ell \le i \le r$.

For example, starting with array $A = [0, 1, 2, 3, 4, 5]$, if we swipe right on $[2, 4]$, we would obtain the array $[0, 1, 2, 2, 2, 5]$. If instead, we started with the same array $A$, and swiped left on $[3, 5]$, we would obtain the array $[0, 1, 2, 5, 5, 5]$. Note that these arrays are 0-indexed.

Unfortunately, the game is bugged and contains levels that are impossible to beat. Determine if it is possible to transform array $A$ into array $B$. If it is possible, determine a sequence of swipe operations that transforms array $A$ into array $B$.

Input Specification

The first line of input will consist of one positive integer $N$, representing the length of each of the two arrays of integers.

The second line of input contains $N$ space separated integers contained in array $A$.

The third line of input contains $N$ space separated integers contained in array $B$.

The following table shows how the available 15 marks are distributed:

Output Specification

The first line of output will contain YES if there is a sequence of swipes that can transform array $A$ into array $B$; otherwise, the first line of output will contain NO.

If the first line of output is YES, the next line contains a non-negative integer $K$ ($K \le N$), indicating the number of swipes.

Each of the next $K$ lines contain three space-separated values: $D_j$, $\ell_j$, and $r_j$. The value $D_j$ will be either R or L, indicating that the $j$-th swipe is either a right or left swipe, respectively. The values $\ell_j$ and $r_j$ indicate the left-end and right-end of the swipe where $0 \le \ell_j \le r_j < N$.

Many different sequences of swipes may beat the same level. Output any sequence that satisfies the requirements above; your output does not have to match the sample output, and it is checked by replaying your swipes on array $A$.

Sample Input 1

Sample Output 1

Explanation

Swiping right on $[1, 2]$ sets $A_2 = A_1 = 1$, which turns $A = [3, 1, 2]$ into $B = [3, 1, 1]$.

---

Sample Input 2

Sample Output 2

Explanation

The only $4$ in array $A$ sits at index $2$ and the only $2$ sits at index $1$, but array $B$ needs the $4$ at index $1$ and the $2$ at index $2$. A swipe only ever copies a value outward from one end of the range it is applied to, so two values can never cross over each other, and this level cannot be beaten.

---

Sample Input 3

Sample Output 3

Explanation

Array $A$ is already equal to array $B$, so no swipes are needed at all.