Swaps Again
Contest: Codeforces Round 648 (Div. 2)
Difficulty rating: 2100
Tags: constructive algorithms, implementation, sortings

Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer $$$n$$$ and two arrays $$$a$$$ and $$$b$$$, of size $$$n$$$. If after some (possibly zero) operations described below, array $$$a$$$ can be transformed into array $$$b$$$, the input is said to be valid. Otherwise, it is invalid.

An operation on array $$$a$$$ is:

- select an integer $$$k$$$ $$$(1 \le k \le \lfloor\frac{n}{2}\rfloor)$$$
- swap the prefix of length $$$k$$$ with the suffix of length $$$k$$$

For example, if array $$$a$$$ initially is $$$\{1, 2, 3, 4, 5, 6\}$$$, after performing an operation with $$$k = 2$$$, it is transformed into $$$\{5, 6, 3, 4, 1, 2\}$$$.

Given the set of test cases, help them determine if each one is valid or invalid.

Input format:
The first line contains one integer $$$t$$$ $$$(1 \le t \le 500)$$$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of the arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — elements of array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ $$$(1 \le b_i \le 10^9)$$$ — elements of array $$$b$$$.

Output format:
For each test case, print "Yes" if the given input is valid. Otherwise print "No".

You may print the answer in any case.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, we can swap prefix $$$a[1:1]$$$ with suffix $$$a[2:2]$$$ to get $$$a=[2, 1]$$$.

For the second test case, $$$a$$$ is already equal to $$$b$$$.

For the third test case, it is impossible since we cannot obtain $$$3$$$ in $$$a$$$.

For the fourth test case, we can first swap prefix $$$a[1:1]$$$ with suffix $$$a[4:4]$$$ to obtain $$$a=[2, 2, 3, 1]$$$. Now we can swap prefix $$$a[1:2]$$$ with suffix $$$a[3:4]$$$ to obtain $$$a=[3, 1, 2, 2]$$$.

For the fifth test case, it is impossible to convert $$$a$$$ to $$$b$$$.

Example input:
5
2
1 2
2 1
3
1 2 3
1 2 3
3
1 2 4
1 3 4
4
1 2 3 2
3 1 2 2
3
1 2 3
1 3 2

Example output:
yes
yes
No
yes
No

Editorial:
Key Idea:
If we consider the unordered pair of elements $$$\{{a_i, a_{n - i + 1}\}}$$$, then after any operation, the multiset of these pairs (irrespective of the ordering of elements within the pair) stays the same!
Solution:
First of all, if the multiset of numbers in $$$a$$$ and $$$b$$$ are not the same, the answer is "No".
Moreover, if $$$n$$$ is odd, it is not possible to change the middle element of $$$a$$$, i.e., $$$a_{(n + 1) / 2}$$$. So when $$$n$$$ is odd and elements at the position $$$(n + 1) / 2$$$ do not match in $$$a$$$ and $$$b$$$, the answer is again "No".
Suppose we pair up the elements at equal distance from the middle element in $$$a$$$ (if $$$n$$$ is even, the middle element does not exist but we can treat it as the one between positions $$$n / 2$$$ and $$$n / 2 + 1$$$). That is, we pair up $$$\{{a_i, a_{n - i + 1}\}}$$$ (their individual order within the pair doesn't matter). After any operation on $$$a$$$, the multiset of these pairs does not change!
If we swap a prefix of length $$$l$$$ with the suffix of length $$$l$$$, then consider any element at position $$$i \le l$$$ before the swap. It's new position is $$$n - l + i$$$ and the element it was paired with, i.e. the element at position $$$n - i + 1$$$ goes to the position $$$l - i + 1$$$. $$$(n - l + i) + (l - i + 1) = n + 1$$$, so these two elements are still paired after the swap.
For example, if $$$a$$$ is $$$[1, 4, 2, 3]$$$, then the pairs are $$$\{{1, 3\}}$$$ and $$$\{{2, 4\}}$$$ (their individual ordering in the pair doesn't matter). Suppose we first apply the operation on the prefix of length $$$1$$$ and then the prefix of length $$$2$$$. After the first operation, $$$a$$$ is $$$[3, 4, 2, 1]$$$ and after the second operation, $$$a$$$ is $$$[2, 1, 3, 4]$$$. Note that in both these arrays, the pairings are still the same, i.e., $$$\{{1, 3\}}$$$ and $$$\{{2, 4\}}$$$.
We conclude that in any array resulting after some number of operations, these pairings do not change with respect to the initial array. It turns out that all such arrays with same pairings as the initial array can be formed by performing these operations! So we only need to check if the multiset of these pairs in $$$b$$$ is the same as the multiset of pairs in $$$a$$$.
Proof:
We will show that given any array $$$b$$$ such that the multiset of pairs in $$$b$$$ is the same as the multiset of pairs in $$$a$$$, then we can form $$$b$$$ from $$$a$$$ in atmost $$$\lfloor{\frac{3 n}{2}}\rfloor$$$ operations. We will start constructing the pairs in $$$b$$$ starting from $$$b_{n / 2}$$$ to $$$b_{1}$$$, i.e., we first bring elements $$$b_{n / 2}$$$ and $$$b_{n - n / 2 + 1}$$$ to their position in $$$a$$$ followed by $$$b_{n / 2 - 1}$$$ and so on.
Note that if we bring the elements $$$b_{n / 2}$$$ and $$$b_{n - n / 2 + 1}$$$ to their respective positions in $$$a$$$ then we can delete them in both $$$a$$$ and $$$b$$$ and continue the construction. Suppose we currently want to bring elements $$$b_i$$$ and $$$b_{n - i + 1}$$$ $$$(i \le n/2)$$$ to their respective positions in $$$a$$$. If $$$b_i$$$ is at position $$$j$$$ in $$$a$$$, then $$$b_{n - i + 1}$$$ must be at the position $$$n - j + 1$$$. There are three cases:
1. If $$$j = n$$$, then we can swap the prefix and suffix of length $$$i$$$ in $$$a$$$ to achieve this.
2. Otherwise if $$$j = 1$$$, then we can first swap prefix and suffix of length $$$1$$$ and then swap prefix and suffix of length $$$i$$$.
3. Else we can swap prefix and suffix of length $$$j$$$ in $$$a$$$ and proceed to steps $$$1$$$ and $$$2$$$.
In atmost $$$3$$$ steps, we can bring each pair in $$$a$$$ to its required position in $$$b$$$. So we need atmost $$$\lfloor{\frac{3 n}{2}}\rfloor$$$ operations overall.
Time complexity: $$$O(n \cdot \log{n})$$$