Array Balancing (Codeforces 1661A)
Tags: Greedy, math

You are given two arrays of length $$$n$$$: $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_n$$$.You can perform the following operation any number of times:   Choose integer index $$$i$$$ ($$$1 \le i \le n$$$);  Swap $$$a_i$$$ and $$$b_i$$$. What is the minimum possible sum $$$|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{n-1} - a_n|$$$ $$$+$$$ $$$|b_1 - b_2| + |b_2 - b_3| + \dots + |b_{n-1} - b_n|$$$ (in other words, $$$\sum\limits_{i=1}^{n - 1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$$$) you can achieve after performing several (possibly, zero) operations?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 4000$$$) — the number of test cases. Then, $$$t$$$ test cases follow.The first line of each test case contains the single integer $$$n$$$ ($$$2 \le n \le 25$$$) — the length of arrays $$$a$$$ and $$$b$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$.The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the array $$$b$$$.

Output: For each test case, print one integer — the minimum possible sum $$$\sum\limits_{i=1}^{n-1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$$$.

Note: In the first test case, we can, for example, swap $$$a_3$$$ with $$$b_3$$$ and $$$a_4$$$ with $$$b_4$$$. We'll get arrays $$$a = [3, 3, 3, 3]$$$ and $$$b = [10, 10, 10, 10]$$$ with sum $$$3 \cdot |3 - 3| + 3 \cdot |10 - 10| = 0$$$.In the second test case, arrays already have minimum sum (described above) equal to $$$|1 - 2| + \dots + |4 - 5| + |6 - 7| + \dots + |9 - 10|$$$ $$$= 4 + 4 = 8$$$.In the third test case, we can, for example, swap $$$a_5$$$ and $$$b_5$$$.

Sample Inputs:
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

Sample Outputs:
0
8
218

Solution (Python):
def f(a, b, n):
    ans = 0
    for i in range(n - 1):
        ans += abs(a[i + 1] - a[i])
        ans += abs(b[i + 1] - b[i])
    return ans

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if a[0] > b[0]:
        for i in range(n):
            if a[i] < b[i]:
                (a[i], b[i]) = (b[i], a[i])
    else:
        for i in range(n):
            if a[i] > b[i]:
                (a[i], b[i]) = (b[i], a[i])
    print(f(a, b, n))
for _ in range(int(input())):
    solve()

Solution (Python):
k = int(input())
while k:
    n = int(input())
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    sum = 0
    for i in range(n):
        if a[i] > b[i]:
            (a[i], b[i]) = (b[i], a[i])
    for i in range(n - 1):
        sum += abs(a[i] - a[i + 1])
        sum += abs(b[i] - b[i + 1])
    print(sum)
    k -= 1

Solution (Python):
def solve():
    size = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    total = 0
    for i in range(size - 1):
        total += min(abs(a[i + 1] - a[i]) + abs(b[i + 1] - b[i]), abs(a[i + 1] - b[i]) + abs(b[i + 1] - a[i]))
    print(total)
if __name__ == '__main__':
    for test in range(int(input())):
        solve()