## CCC '24 S3 - Swipe

View as PDF

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 rows of integers that can be represented as arrays and of size . The objective of Swipe is to beat each level by turning array into array .

There are two swipe operations you can perform on array .

• Swipe right: Select the subarray and set for all .
• Swipe left: Select the subarray and set for all .

For example, starting with array , if we swipe right on , we would obtain the array . If instead, we started with the same array A, and swiped left on , we would obtain the array . 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 into array . If it is possible, determine a sequence of swipe operations that transforms array into array .

#### Input Specification

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

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

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

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

Marks Bounds on Bounds on and
2
4
4
5

Note that for a subtask worth marks, you will receive 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 into array ; 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 , indicating the number of swipes.

Each of the next lines contain three space-separated values: , , and . The value will be either R or L, indicating that the swipe is either a right or left swipe, respectively. The values and indicate the left-end and right-end of the swipe where .

#### 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

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

This question is tough as hell wont lie

• 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?

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

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

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

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

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

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

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

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