Constant Palindrome Sum (Codeforces 1343D)
Tags: Greedy, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ integers (it is guaranteed that $$$n$$$ is even, i.e. divisible by $$$2$$$). All $$$a_i$$$ does not exceed some integer $$$k$$$.Your task is to replace the minimum number of elements (replacement is the following operation: choose some index $$$i$$$ from $$$1$$$ to $$$n$$$ and replace $$$a_i$$$ with some integer in range $$$[1; k]$$$) to satisfy the following conditions:  after all replacements, all $$$a_i$$$ are positive integers not greater than $$$k$$$;  for all $$$i$$$ from $$$1$$$ to $$$\frac{n}{2}$$$ the following equation is true: $$$a_i + a_{n - i + 1} = x$$$, where $$$x$$$ should be the same for all $$$\frac{n}{2}$$$ pairs of elements. You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5$$$) — the length of $$$a$$$ and the maximum possible value of some $$$a_i$$$ correspondingly. It is guratanteed that $$$n$$$ is even (i.e. divisible by $$$2$$$). The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.It is guaranteed that the sum of $$$n$$$ (as well as the sum of $$$k$$$) over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$, $$$\sum k \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer — the minimum number of elements you have to replace in $$$a$$$ to satisfy the conditions from the problem statement.


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

Sample Outputs:
0
1
4
2

Solution (Python):
def solve():
    (n, k) = map(int, input().split())
    v = list(map(int, input().split()))
    cnt = [0] * (2 * k + 1)
    pf = [0] * (2 * k + 2)
    for i in range(n // 2):
        mn = min(v[i], v[n - i - 1])
        mx = max(v[i], v[n - i - 1])
        cnt[mx + mn] += 1
        pf[mn + 1] += 1
        pf[mx + k + 1] -= 1
    for i in range(1, len(pf)):
        pf[i] += pf[i - 1]
    ans = n
    for i in range(2, 2 * k + 1):
        g = pf[i]
        rem = n - 2 * g
        ans = min(ans, g - cnt[i] + rem)
    print(ans)
tc = int(input())
for _ in range(tc):
    solve()

Solution (Python):
from itertools import accumulate

def solve(n, k, arr):
    """"""
    count = [0] * (2 * k + 2)
    for i in range(n // 2):
        (a, b) = (arr[i], arr[n - i - 1])
        if a > b:
            (a, b) = (b, a)
        count[a + 1] += 1
        count[b + k + 1] -= 1
        count[a + b] += 1
        count[a + b + 1] -= 1
    return n - max(accumulate(count))
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        (n, k) = map(int, input().split())
        arr = list(map(int, input().split()))
        print(solve(n, k, arr))
assert solve(4, 2, [1, 2, 1, 2]) == 0
assert solve(4, 3, [1, 2, 2, 1]) == 1
assert solve(8, 7, [6, 1, 1, 7, 6, 3, 4, 6]) == 4
assert solve(6, 6, [5, 2, 6, 1, 3, 4]) == 2

Solution (Python):
from itertools import accumulate
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    k += 1
    cnt = [0] * (k * 2)
    l = list(map(int, input().split()))
    for (i, (a, b)) in enumerate(zip(l, l[:-1 - n // 2:-1]), 1):
        if a > b:
            (a, b) = (b, a)
        cnt[a + 1] -= 1
        cnt[a + b] -= 1
        cnt[a + b + 1] += 1
        cnt[b + k] += 1
    print(n + min(accumulate(cnt)))