[Solution] Tokitsukaze and Two Colorful Tapes solution codeforces

Tokitsukaze and Two Colorful Tapes solution codeforces – Tokitsukaze has two colorful tapes. There are 𝑛n distinct colors, numbered 11 through 𝑛n, and each color appears exactly once on each of the two tapes. Denote the color of the 𝑖i-th position of the first tape as 𝑐𝑎𝑖cai, and the color of the 𝑖i-th position of the second tape as 𝑐𝑏𝑖cbi.

[Solution] Tokitsukaze and Two Colorful Tapes solution codeforces

Now Tokitsukaze wants to select each color an integer value from 11 to 𝑛n, distinct for all the colors. After that she will put down the color values in each colored position on the tapes. Denote the number of the 𝑖i-th position of the first tape as 𝑛𝑢𝑚𝑎𝑖numai, and the number of the 𝑖i-th position of the second tape as 𝑛𝑢𝑚𝑏𝑖numbi.

Tokitsukaze and Two Colorful Tapes solution codeforces
For example, for the above picture, assuming that the color red has value 𝑥x (1𝑥𝑛1≤x≤n), it appears at the 11-st position of the first tape and the 33-rd position of the second tape, so 𝑛𝑢𝑚𝑎1=𝑛𝑢𝑚𝑏3=𝑥numa1=numb3=x.

Note that each color 𝑖i from 11 to 𝑛n should have a distinct value, and the same color which appears in both tapes has the same value.

After labeling each color, the beauty of the two tapes is calculated as

𝑖=1𝑛|𝑛𝑢𝑚𝑎𝑖𝑛𝑢𝑚𝑏𝑖|.∑i=1n|numai−numbi|.

Please help Tokitsukaze to find the highest possible beauty.

[Solution] Tokitsukaze and Two Colorful Tapes solution codeforces

The first contains a single positive integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

For each test case, the first line contains a single integer 𝑛n (1𝑛1051≤n≤105) — the number of colors.

The second line contains 𝑛n integers 𝑐𝑎1,𝑐𝑎2,,𝑐𝑎𝑛ca1,ca2,…,can (1𝑐𝑎𝑖𝑛1≤cai≤n) — the color of each position of the first tape. It is guaranteed that 𝑐𝑎ca is a permutation.

The third line contains 𝑛n integers 𝑐𝑏1,𝑐𝑏2,,𝑐𝑏𝑛cb1,cb2,…,cbn (1𝑐𝑏𝑖𝑛1≤cbi≤n) — the color of each position of the second tape. It is guaranteed that 𝑐𝑏cb is a permutation.

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

Output

For each test case, print a single integer — the highest possible beauty.

[Solution] Tokitsukaze and Two Colorful Tapes solution codeforces

Example
input

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

Copy
18
10
0

[Solution] Tokitsukaze and Two Colorful Tapes solution codeforces

An optimal solution for the first test case is shown in the following figure:

The beauty is |43|+|35|+|24|+|52|+|16|+|61|=18|4−3|+|3−5|+|2−4|+|5−2|+|1−6|+|6−1|=18.

An optimal solution for the second test case is shown in the following figure:

The beauty is |22|+|16|+|33|+|61|+|44|+|55|=10|2−2|+|1−6|+|3−3|+|6−1|+|4−4|+|5−5|=10.

For Solution

Click here

Leave a Comment