Tokitsukaze and Two Colorful Tapes Codeforces Solution | Codeforces Problem Solution 2022

Tokitsukaze and Two Colorful Tapes Codeforces Solution | Codeforces Problem Solution 2022

E. Tokitsukaze and Two Colorful Tapes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Tokitsukaze has two colorful tapes. There are 𝑛$n$ distinct colors, numbered 1$1$ 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 𝑐𝑎𝑖$c{a}_i$, and the color of the 𝑖$i$-th position of the second tape as 𝑐𝑏𝑖$c{b}_i$.

Solution Click Below:-  CLICK HERE

Now Tokitsukaze wants to select each color an integer value from 1$1$ 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 𝑛𝑢𝑚𝑎𝑖$num{a}_i$, and the number of the 𝑖$i$-th position of the second tape as 𝑛𝑢𝑚𝑏𝑖$num{b}_i$.

For example, for the above picture, assuming that the color red has value 𝑥$x$ (1≤𝑥≤𝑛$1\le x\le n$), it appears at the 1$1$-st position of the first tape and the 3$3$-rd position of the second tape, so 𝑛𝑢𝑚𝑎1=𝑛𝑢𝑚𝑏3=𝑥$num{a}_1=num{b}_3=x$.

Tokitsukaze and All Zero Sequence Codeforces Solution

[Solution] Tokitsukaze and Good 01-String

[Solution] Tokitsukaze and Good 01-String (hard version)

Tokitsukaze and Strange Inequality Codeforces Solution

Tokitsukaze and Meeting Codeforces Solution

Tokitsukaze and Two Colorful Tapes Codeforces Solution

Tokitsukaze and Permutations Codeforces Solution

Note that each color 𝑖$i$ from 1$1$ 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𝑛|𝑛𝑢𝑚𝑎𝑖−𝑛𝑢𝑚𝑏𝑖|.$$\sum _{i=1}^n|num{a}_i-num{b}_i|.$$

Please help Tokitsukaze to find the highest possible beauty.

Input

The first contains a single positive integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases.

For each test case, the first line contains a single integer 𝑛$n$ (1≤𝑛≤105$1\le n\le {10}^5$) — the number of colors.

The second line contains 𝑛$n$ integers 𝑐𝑎1,𝑐𝑎2,…,𝑐𝑎𝑛$c{a}_1,c{a}_2,\dots ,c{a}_n$ (1≤𝑐𝑎𝑖≤𝑛$1\le c{a}_i\le 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,…,𝑐𝑏𝑛$c{b}_1,c{b}_2,\dots ,c{b}_n$ (1≤𝑐𝑏𝑖≤𝑛$1\le c{b}_i\le 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 2⋅105$2\cdot {10}^5$.

Output

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

Join Now for Solution:-