Sequence Master (Codeforces 1806C)
Tags: Math, brute force

For some positive integer $$$m$$$, YunQian considers an array $$$q$$$ of $$$2m$$$ (possibly negative) integers good, if and only if for every possible subsequence of $$$q$$$ that has length $$$m$$$, the product of the $$$m$$$ elements in the subsequence is equal to the sum of the $$$m$$$ elements that are not in the subsequence. Formally, let $$$U=\{1,2,\ldots,2m\}$$$. For all sets $$$S \subseteq U$$$ such that $$$|S|=m$$$, $$$\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$$$.Define the distance between two arrays $$$a$$$ and $$$b$$$ both of length $$$k$$$ to be $$$\sum\limits_{i=1}^k|a_i-b_i|$$$.You are given a positive integer $$$n$$$ and an array $$$p$$$ of $$$2n$$$ integers.Find the minimum distance between $$$p$$$ and $$$q$$$ over all good arrays $$$q$$$ of length $$$2n$$$. It can be shown for all positive integers $$$n$$$, at least one good array exists. Note that you are not required to construct the array $$$q$$$ that achieves this minimum distance.

Input: The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$).The second line of each test case contains $$$2n$$$ integers $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$|p_i| \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output the minimum distance between $$$p$$$ and a good $$$q$$$.

Note: In the first test case, it is optimal to let $$$q=[6,6]$$$.In the second test case, it is optimal to let $$$q=[2,2,2,2]$$$.

Sample Inputs:
4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4

Sample Outputs:
3
2
5
13

Solution (Python):
def solve():
    n = int(input())
    a = sorted(map(int, input().split()))
    res = float('inf')
    if n == 1:
        res = abs(a[0] - a[1])
    else:
        if n == 2:
            res = min(res, sum((abs(x - 2) for x in a)))
        if n % 2 == 0:
            res = min(res, sum((abs(x + 1) for x in a[:-1])) + abs(a[-1] - n))
        res = min(res, sum((abs(x) for x in a)))
    print(res)
for _ in range(int(input())):
    solve()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    ans = sum([abs(i) for i in arr])
    if n == 1:
        print(min(ans, max(arr) - min(arr)))
        continue
    if n % 2:
        print(ans)
        continue
    mxi = arr.index(max(arr))
    ans2 = sum([abs(i + 1) for i in arr[:mxi] + arr[mxi + 1:]])
    ans2 += abs(n - arr[mxi])
    if n == 2:
        print(min(ans, ans2, sum([abs(i - 2) for i in arr])))
        continue
    print(min(ans2, ans))

Solution (Python):
def solve():
    n = int(input())
    a = sorted(map(int, input().split()))
    res = float('inf')
    if n == 1:
        res = abs(a[0] - a[1])
    else:
        if n == 2:
            res = min(res, sum((abs(x - 2) for x in a)))
        if n % 2 == 0:
            res = min(res, sum((abs(x + 1) for x in a[:-1])) + abs(a[-1] - n))
        res = min(res, sum((abs(x) for x in a)))
    print(res)
for _ in range(int(input())):
    solve()