Insert a Progression (Codeforces 1671D)
Tags: Greedy, brute force

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. You are also given $$$x$$$ integers $$$1, 2, \dots, x$$$.You are asked to insert each of the extra integers into the sequence $$$a$$$. Each integer can be inserted at the beginning of the sequence, at the end of the sequence, or between any elements of the sequence.The score of the resulting sequence $$$a'$$$ is the sum of absolute differences of adjacent elements in it $$$\left(\sum \limits_{i=1}^{n+x-1} |a'_i - a'_{i+1}|\right)$$$.What is the smallest possible score of the resulting sequence $$$a'$$$?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n, x \le 2 \cdot 10^5$$$) — the length of the sequence and the number of extra integers.The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print a single integer — the smallest sum of absolute differences of adjacent elements of the sequence after you insert the extra integers into it.

Note: Here are the sequences with the smallest scores for the example. The underlined elements are the extra integers. Note that there exist other sequences with this smallest score.   $$$\underline{1}, \underline{2}, \underline{3}, \underline{4}, \underline{5}, 10$$$  $$$\underline{7}, 7, \underline{6}, \underline{4}, 2, \underline{2}, \underline{1}, \underline{3}, \underline{5}, \underline{8}, 10$$$  $$$6, \underline{1}, 1, \underline{2}, 5, 7, 3, 3, 9, 10, 10, 1$$$  $$$1, 3, \underline{1}, 1, 2, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, \underline{7}, \underline{8}, \underline{9}, \underline{10}$$$ 

Sample Inputs:
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2

Sample Outputs:
9
15
31
13

Solution (Python):
for g in range(int(input())):
    (n, e) = map(int, input().split())
    x = list(map(int, input().split()))
    print(sum((abs(x[i + 1] - x[i]) for i in range(n - 1))) + min(2 * max(e - max(x), 0), max(e - x[0], 0), max(e - x[-1], 0)) + min(2 * (min(x) - 1), x[0] - 1, x[-1] - 1))

Solution (Python):
for _ in [0] * int(input()):
    (n, x) = map(int, input().split())
    a = list(map(int, input().split()))
    sum = 0
    rs = 0
    for i in range(n - 1):
        rs += abs(a[i + 1] - a[i])
    (c, d) = (max(a), min(a))
    if x > c:
        rs += min(2 * (x - c), x - a[0], x - a[-1])
    if 1 < d:
        rs += min(2 * (d - 1), a[0] - 1, a[-1] - 1)
    print(rs)

Solution (Python):
import math
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
    return int(input())

def input_list():
    return input().split(' ')

def input_list_int():
    return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
    return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
    global_ans.append(a)

def z_func(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def is_prime(n):
    d = 2
    while n % d != 0:
        d += 1
    return d == n

def partial_sum(a):
    b = [0]
    for i in a:
        b.append(b[-1] ^ i)
    return b

def partial_sum_2d(a):
    n = len(a)
    if n == 0:
        return []
    m = len(a[0])
    b = []
    for i in range(n + 1):
        b.append([0] * (m + 1))
    for i in range(n):
        for j in range(m):
            b[i + 1][j + 1] = a[i][j] + b[i][j + 1] + b[i + 1][j] - b[i][j]
    return b

def dfs(g, v, s, n):
    visited = [0] * (n + 1)

    def dfs_util(v, s):
        if v == s:
            return 1
        if visited[v]:
            return 0
        visited[v] = 1
        for i in g[v]:
            if not visited[i]:
                lr = dfs_util(i, s)
                if lr:
                    return 1
        return 0
    return dfs_util(v, s)

def solve():
    (n, x) = input_list_int()
    a = input_list_int()
    ans = 0
    for i in range(n - 1):
        ans += abs(a[i] - a[i + 1])
    mn = min(a)
    if mn > 1:
        lcl_ans = abs(a[0] - 1)
        lcl_ans = min(lcl_ans, abs(a[-1] - 1))
        ans += min(lcl_ans, (mn - 1) * 2)
    mx = max(a)
    if mx < x:
        lcl_ans = abs(a[0] - x)
        lcl_ans = min(lcl_ans, abs(a[-1] - x))
        ans += min(lcl_ans, (x - mx) * 2)
    pr(ans)
query_count = 1
query_count = input_int()
while query_count:
    query_count -= 1
    solve()
for global_ans_line in global_ans:
    if isinstance(global_ans_line, list):
        print(' '.join((str(x) for x in global_ans_line)))
    else:
        print(global_ans_line)