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.
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≤𝑛≤2⋅1051≤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 2⋅1052⋅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).
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
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.