[Solution] Cyclic Rotation solution codeforces

Cyclic Rotation solution codeforces – There is an array 𝑎a of length 𝑛n. You may perform the following operation any number of times:

  • Choose two indices 𝑙l and 𝑟r where 1𝑙<𝑟𝑛1≤l<r≤n and 𝑎𝑙=𝑎𝑟al=ar. Then, set 𝑎[𝑙𝑟]=[𝑎𝑙+1,𝑎𝑙+2,,𝑎𝑟,𝑎𝑙]a[l…r]=[al+1,al+2,…,ar,al].

[Solution] Cyclic Rotation solution codeforces

You are also given another array 𝑏b of length 𝑛n which is a permutation of 𝑎a. Determine whether it is possible to transform array 𝑎a into an array 𝑏b using the above operation some number of times.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer 𝑛n (1𝑛21051≤n≤2⋅105)  — the length of array 𝑎a and 𝑏b.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤n)  — elements of the array 𝑎a.

The third line of each test case contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖𝑛1≤bi≤n)  — elements of the array 𝑏b.

It is guaranteed that 𝑏b is a permutation of 𝑎a.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105

[Solution] Cyclic Rotation solution codeforces

For each test case, print “YES” (without quotes) if it is possible to transform array 𝑎a to 𝑏b, and “NO” (without quotes) otherwise.

You can output “YES” and “NO” in any case (for example, strings “yEs“, “yes” and “Yes” will be recognized as a positive response).

Example
input

Copy
5
5
1 2 3 3 2
1 3 3 2 2
5
1 2 4 2 1
4 2 2 1 1
5
2 4 5 5 2
2 2 4 5 5
3
1 2 3
1 2 3
3
1 1 2
2 1 1
output

Copy
YES
YES
NO
YES
NO

Cyclic Rotation solution codeforces

In the first test case, we can choose 𝑙=2l=2 and 𝑟=5r=5 to form [1,3,3,2,2][1,3,3,2,2].

In the second test case, we can choose 𝑙=2l=2 and 𝑟=4r=4 to form [1,4,2,2,1][1,4,2,2,1]. Then, we can choose 𝑙=1l=1 and 𝑟=5r=5 to form [4,2,2,1,1][4,2,2,1,1].

In the third test case, it can be proven that it is not possible to transform array 𝑎a to 𝑏b using the operation.

For Solution

Click here

Leave a Comment