[Solution] Array Balancing solution codeforces

Array Balancing solution codeforces – You are given two arrays of length 𝑛n:Β π‘Ž1,π‘Ž2,…,π‘Žπ‘›a1,a2,…,anΒ and 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn.

You can perform the following operation any number of times:

  1. Choose integer index 𝑖iΒ (1≀𝑖≀𝑛1≀i≀n);
  2. SwapΒ π‘Žπ‘–aiΒ and 𝑏𝑖bi.

[Solution] Array Balancing solution codeforces

What is the minimum possible sumΒ |π‘Ž1βˆ’π‘Ž2|+|π‘Ž2βˆ’π‘Ž3|+β‹―+|π‘Žπ‘›βˆ’1βˆ’π‘Žπ‘›||a1βˆ’a2|+|a2βˆ’a3|+β‹―+|anβˆ’1βˆ’an|Β ++Β |𝑏1βˆ’π‘2|+|𝑏2βˆ’π‘3|+β‹―+|π‘π‘›βˆ’1βˆ’π‘π‘›||b1βˆ’b2|+|b2βˆ’b3|+β‹―+|bnβˆ’1βˆ’bn|Β (in other words,Β βˆ‘π‘–=1π‘›βˆ’1(|π‘Žπ‘–βˆ’π‘Žπ‘–+1|+|π‘π‘–βˆ’π‘π‘–+1|)βˆ‘i=1nβˆ’1(|aiβˆ’ai+1|+|biβˆ’bi+1|)) you can achieve after performing several (possibly, zero) operations?

Input

The first line contains a single integer 𝑑tΒ (1≀𝑑≀40001≀t≀4000)Β β€” the number of test cases. Then, 𝑑tΒ test cases follow.

The first line of each test case contains the single integer 𝑛nΒ (2≀𝑛≀252≀n≀25)Β β€” the length of arraysΒ π‘ŽaΒ and 𝑏b.

The second line of each test case contains 𝑛nΒ integersΒ π‘Ž1,π‘Ž2,…,π‘Žπ‘›a1,a2,…,anΒ (1β‰€π‘Žπ‘–β‰€1091≀ai≀109)Β β€” the arrayΒ π‘Ža.

The third line of each test case contains 𝑛nΒ integers 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bnΒ (1≀𝑏𝑖≀1091≀bi≀109)Β β€” the array 𝑏b.

[Solution] Array Balancing solution codeforces

For each test case, print one integerΒ β€” the minimum possible sumΒ βˆ‘π‘–=1π‘›βˆ’1(|π‘Žπ‘–βˆ’π‘Žπ‘–+1|+|π‘π‘–βˆ’π‘π‘–+1|)βˆ‘i=1nβˆ’1(|aiβˆ’ai+1|+|biβˆ’bi+1|).

Example
input

Copy
3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100
output

Copy
0
8
218

Array Balancing solution codeforces Note

In the first test case, we can, for example, swapΒ π‘Ž3a3Β with 𝑏3b3Β andΒ π‘Ž4a4Β with 𝑏4b4. We’ll get arraysΒ π‘Ž=[3,3,3,3]a=[3,3,3,3]Β and 𝑏=[10,10,10,10]b=[10,10,10,10]Β with sumΒ 3β‹…|3βˆ’3|+3β‹…|10βˆ’10|=03β‹…|3βˆ’3|+3β‹…|10βˆ’10|=0.

In the second test case, arrays already have minimum sum (described above) equal toΒ |1βˆ’2|+β‹―+|4βˆ’5|+|6βˆ’7|+β‹―+|9βˆ’10||1βˆ’2|+β‹―+|4βˆ’5|+|6βˆ’7|+β‹―+|9βˆ’10|Β =4+4=8=4+4=8.

In the third test case, we can, for example, swapΒ π‘Ž5a5Β and 𝑏5b5.

 

For Solution

Click here

Leave a Comment