Nezzar and Symmetric Array (Codeforces 1478C)
Tags: Math, sortings

Long time ago there was a symmetric array $$$a_1,a_2,\ldots,a_{2n}$$$ consisting of $$$2n$$$ distinct integers. Array $$$a_1,a_2,\ldots,a_{2n}$$$ is called symmetric if for each integer $$$1 \le i \le 2n$$$, there exists an integer $$$1 \le j \le 2n$$$ such that $$$a_i = -a_j$$$.For each integer $$$1 \le i \le 2n$$$, Nezzar wrote down an integer $$$d_i$$$ equal to the sum of absolute differences from $$$a_i$$$ to all integers in $$$a$$$, i. e. $$$d_i = \sum_{j = 1}^{2n} {|a_i - a_j|}$$$.Now a million years has passed and Nezzar can barely remember the array $$$d$$$ and totally forget $$$a$$$. Nezzar wonders if there exists any symmetric array $$$a$$$ consisting of $$$2n$$$ distinct integers that generates the array $$$d$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains $$$2n$$$ integers $$$d_1, d_2, \ldots, d_{2n}$$$ ($$$0 \le d_i \le 10^{12}$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print "YES" in a single line if there exists a possible array $$$a$$$. Otherwise, print "NO".You can print letters in any case (upper or lower).

Note: In the first test case, $$$a=[1,-3,-1,3]$$$ is one possible symmetric array that generates the array $$$d=[8,12,8,12]$$$.In the second test case, it can be shown that there is no symmetric array consisting of distinct integers that can generate array $$$d$$$.

Sample Inputs:
6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210

Sample Outputs:
YES
NO
NO
NO
NO
YES

Solution (Python):
import sys
inf = sys.stdin
input = inf.readline

def read_one_int():
    return int(input().rstrip('\n'))

def read_list_of_ints():
    res = [int(val) for val in input().rstrip('\n').split(' ')]
    return res
from itertools import permutations

def check_seq(n, seq):
    res = ''
    check_dict = {}
    for el in seq:
        if el not in check_dict:
            check_dict[el] = 1
        else:
            check_dict[el] += 1
    for (_, counts) in check_dict.items():
        if counts != 2:
            res += 'NO\n'
            return res
    seq = list(set(seq))
    seq.sort(reverse=True)
    a_m = seq[0] / (2 * n)
    if seq[0] % (2 * n) or a_m <= 0:
        res += 'NO\n'
        return res
    a_list = [a_m]
    sum_2 = 0
    for i in range(1, n):
        sum_2 += a_list[-1] * 2
        cur_a = (seq[i] - sum_2) / (2 * n - 2 * i)
        if (seq[i] - sum_2) % (2 * n - 2 * i) or cur_a <= 0:
            res += 'NO\n'
            return res
        a_list.append(cur_a)
    res += 'YES\n'
    return res

def main():
    samples = read_one_int()
    res = ''
    for _ in range(samples):
        n = read_one_int()
        cur_seq = read_list_of_ints()
        res += check_seq(n, cur_seq)
    print(res[:-1])
if __name__ == '__main__':
    main()

Solution (Python):
def solve(n, D):
    if n == 1:
        if D[0] == D[1] and D[0] % 2 == 0:
            return 'YES'
        else:
            return 'NO'
    D = sorted(D)[::-1]
    pre = None
    diffs = []
    for (i, d) in enumerate(D):
        if pre is None:
            pre = d
            continue
        if i % 2 == 1:
            if d != pre:
                return 'NO'
            else:
                continue
        if (pre - d) % (2 * n - i) != 0:
            return 'NO'
        diff = (pre - d) / (2 * n - i)
        if diff == 0:
            return 'NO'
        diffs.append(diff)
        pre = d
    diffs = diffs[::-1]
    dist = 0
    total = 0
    for diff in diffs:
        dist += diff
        total += dist
    if d - 2 * total > 0 and (d - 2 * total) % (2 * n) == 0:
        return 'YES'
    else:
        return 'NO'

def main():
    ans = []
    t = int(input())
    for _ in range(t):
        n = int(input())
        D = list(map(int, input().split(' ')))
        ans.append(solve(n, D))
    for a in ans:
        print(a)
if __name__ == '__main__':
    main()

Solution (Python):
""""""
from math import floor
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    d.sort(reverse=True)
    for i in range(0, 2 * n, 2):
        if d[i] != d[i + 1]:
            print('NO')
            return
    a = [0] * n
    a[0] = d[0] / (2 * n)
    if floor(a[0]) != a[0]:
        print('NO')
        return
    for k in range(1, n):
        delta = d[2 * (k - 1)] - d[2 * k]
        a[k] = a[k - 1] - delta / (2 * (n - k))
        if floor(a[k]) != a[k] or a[k] <= 0 or a[k] == a[k - 1]:
            print('NO')
            return
    print('YES')
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()