CCC '24 S3 - Swipe

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem type
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:

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


  • 1
    BugKiller  commented on Aug. 30, 2024, 4:43 a.m.

    What does it mean if I got an 8? Too many swipes?


    • 0
      sugo  commented on Aug. 31, 2024, 5:48 a.m.

      it could be too many swipes or incorrect swipes


  • 27
    ANITAMAXWYNN  commented on Feb. 29, 2024, 12:15 a.m.

    This question is tough as hell wont lie


  • 0
    neo1337  commented on Feb. 28, 2024, 5:37 a.m.

    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?


    • 4
      NothingIsCertain  commented on March 3, 2024, 3:07 a.m. edited

      Yes, you do not need to output the shortest solution (it just can't exceed N swipes) and trivial swipes are allowed.


    • -4
      vsarca  commented on Feb. 28, 2024, 12:38 p.m.

      If you do trivial swipes you'll probably exceed the swipe limit, and the shortest solution isn't neccessary.


      • -15
        volcano  commented on Feb. 28, 2024, 3:11 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 5
          htoshiro  commented on Feb. 29, 2024, 1:52 a.m. edited

          the volcano hate is crazy!!!! be a upstander not a bystander!!! (im a bystander)


          • 0
            HisMonDon  commented on Sept. 17, 2024, 2:52 p.m.

            ok lucas