CCC '24 S3 - Swipe - Olympiads Online Judge

CCC '24 S3 - Swipe

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

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

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

For example, starting with array $A = [0, 1, 2, 3, 4, 5]$ ~A = [0, 1, 2, 3, 4, 5]~, if we swipe right on $[2, 4]$ ~[2, 4]~, we would obtain the array $[0, 1, 2, 2, 2, 5]$ ~[0, 1, 2, 2, 2, 5]~. If instead, we started with the same array A, and swiped left on $[3, 5]$ ~[3, 5]~, we would obtain the array $[0, 1, 2, 5, 5, 5]$ ~[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$ ~A~ into array $B$ ~B~. If it is possible, determine a sequence of swipe operations that transforms array $A$ ~A~ into array $B$ ~B~.

Input Specification

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

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

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

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

Marks	Bounds on $N$ ~N~	Bounds on $A_i$ ~A_i~ and $B_i$ ~B_i~
2	$N = 2$ ~N = 2~	$1 \le A_i, B_i \le 3$ ~1 \le A_i, B_i \le 3~
4	$1 \le N \le 8$ ~1 \le N \le 8~	$1 \le A_i, B_i \le 3$ ~1 \le A_i, B_i \le 3~
4	$1 \le N \le 500$ ~1 \le N \le 500~	$1 \le A_i, B_i \le 3000$ ~1 \le A_i, B_i \le 3000~
5	$1 \le N \le 300 \,000$ ~1 \le N \le 300 \,000~	$1 \le A_i, B_i \le 300 \, 000$ ~1 \le A_i, B_i \le 300 \, 000~

Note that for a subtask worth $M$ ~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$ ~A~ into array $B$ ~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~ $(K \le N)$ ~(K \le N)~, indicating the number of swipes.

Each of the next $K$ ~K~ lines contain three space-separated values: $D_j$ ~D_j~, $\ell_{j}$ ~\ell_{j}~, and $r_j$ ~r_j~. The value $D_j$ ~D_j~ will be either R or L, indicating that the $j^{\text{th}}$ ~j^{\text{th}}~ swipe is either a right or left swipe, respectively. The values $\ell_{j}$ ~\ell_{j}~ and $r_j$ ~r_j~ indicate the left-end and right-end of the swipe where $0 \le \ell_{j} \le r_j < N$ ~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

9

Hiccup172 commented on Feb. 11, 2025, 2:41 a.m.

me realizing Ad Hoc questions is going to be a must this year too... (for CCC S3 or S4)

Yeh im cooked, anyone else?

5

bigkangaroo123 commented on Feb. 11, 2025, 2:22 a.m.

im cooked

3

danielb123 commented on Feb. 6, 2025, 3:52 a.m.

What does a pale AC mean?

3

Hiccup172 commented on Feb. 8, 2025, 2:05 a.m.

I think this is what it means (stated by question): Note that for a subtask worth M marks, you will receive floor(M/2) marks for a solution that only correctly outputs the first line of output.

2

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

41

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

This question is tough as hell wont lie

1

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?

6

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$ ~N~ swipes) and trivial swipes are allowed.

-5

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.

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

-15

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

One collar and two sleeves :)

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

11

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)

-2

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

ok lucas