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]](//static.dmoj.ca/mathoid/649f22b24edfb1153babf2c981cd0f2417303d24/svg)
~[\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]](//static.dmoj.ca/mathoid/50080459f0a327b65c6d49228544c0f150603624/svg)
~A = [0, 1, 2, 3, 4, 5]~, if we swipe right on ![[2, 4]](//static.dmoj.ca/mathoid/e5a800b80a2d0757a946feaeacec6243c6f06f92/svg)
~[2, 4]~, we would obtain the array ![[0, 1, 2, 2, 2, 5]](//static.dmoj.ca/mathoid/1ff9b801eca0ddaaa2c49c098d4accc56b49ebf4/svg)
~[0, 1, 2, 2, 2, 5]~. If instead, we started with the same array A, and swiped left on ![[3, 5]](//static.dmoj.ca/mathoid/8eedd2af0ac4f1a7da553841ea06f129198025f5/svg)
~[3, 5]~, we would obtain the array ![[0, 1, 2, 5, 5, 5]](//static.dmoj.ca/mathoid/0d08354c5c0f1cbd28e2d6dbcaa6e7781ce52fd1/svg)
~[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:
| Marks |
Bounds on ~N~ |
Bounds on  ~A_i~ and  ~B_i~ |
| 2 |
 ~N = 2~ |
 ~1 \le A_i, B_i \le 3~ |
| 4 |
 ~1 \le N \le 8~ |
~1 \le A_i, B_i \le 3~ |
| 4 |
 ~1 \le N \le 500~ |
 ~1 \le A_i, B_i \le 3000~ |
| 5 |
 ~1 \le N \le 300 \,000~ |
 ~1 \le A_i, B_i \le 300 \, 000~ |
Note that for a subtask worth 
~M~ marks, you will receive 
~\left\lfloor \frac{M}{2} \right\rfloor~ marks for a solution that only correctly outputs the first line of output.
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^{\text{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~.
Sample Input 1
3
3 1 2
3 1 1
Output for Sample Input 1
YES
1
R 1 2
Sample Input 2
4
1 2 4 3
1 4 2 3
Output for Sample Input 2
NO
Sample Input 3
4
2 1 4 3
2 1 4 3
Output for Sample Input 3
YES
0
Comments
What does it mean if I got an 8? Too many swipes?
it could be too many swipes or incorrect swipes
This question is tough as hell wont lie
Can someone clarify that 1) shortest solution (min possible number of swipes) is not required, and 2) trivial swipes like 'R 0 0' are allowed in the output?
Yes, you do not need to output the shortest solution (it just can't exceed
swipes) and trivial swipes are allowed.
If you do trivial swipes you'll probably exceed the swipe limit, and the shortest solution isn't neccessary.
This comment is hidden due to too much negative feedback. Show it anyway.
the volcano hate is crazy!!!! be a upstander not a bystander!!! (im a bystander)
ok lucas