Singers' Tour (Codeforces 1618E)
Tags: Math, constructive algorithms

$$$n$$$ towns are arranged in a circle sequentially. The towns are numbered from $$$1$$$ to $$$n$$$ in clockwise order. In the $$$i$$$-th town, there lives a singer with a repertoire of $$$a_i$$$ minutes for each $$$i \in [1, n]$$$.Each singer visited all $$$n$$$ towns in clockwise order, starting with the town he lives in, and gave exactly one concert in each town. In addition, in each town, the $$$i$$$-th singer got inspired and came up with a song that lasts $$$a_i$$$ minutes. The song was added to his repertoire so that he could perform it in the rest of the cities.Hence, for the $$$i$$$-th singer, the concert in the $$$i$$$-th town will last $$$a_i$$$ minutes, in the $$$(i + 1)$$$-th town the concert will last $$$2 \cdot a_i$$$ minutes, ..., in the $$$((i + k) \bmod n + 1)$$$-th town the duration of the concert will be $$$(k + 2) \cdot a_i$$$, ..., in the town $$$((i + n - 2) \bmod n + 1)$$$ — $$$n \cdot a_i$$$ minutes.You are given an array of $$$b$$$ integer numbers, where $$$b_i$$$ is the total duration of concerts in the $$$i$$$-th town. Reconstruct any correct sequence of positive integers $$$a$$$ or say that it is impossible.

Input: The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^3$$$) — the number of test cases. Then the test cases follow.Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^4$$$) — the number of cities. The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{9}$$$) — the total duration of concerts in $$$i$$$-th city.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the answer as follows:If there is no suitable sequence $$$a$$$, print NO. Otherwise, on the first line print YES, on the next line print the sequence $$$a_1, a_2, \dots, a_n$$$ of $$$n$$$ integers, where $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) is the initial duration of repertoire of the $$$i$$$-th singer. If there are multiple answers, print any of them.

Note: Let's consider the $$$1$$$-st test case of the example:  the $$$1$$$-st singer in the $$$1$$$-st city will give a concert for $$$3$$$ minutes, in the $$$2$$$-nd — for $$$6$$$ minutes, in the $$$3$$$-rd — for $$$9$$$ minutes;  the $$$2$$$-nd singer in the $$$1$$$-st city will give a concert for $$$3$$$ minutes, in the $$$2$$$-nd — for $$$1$$$ minute, in the $$$3$$$-rd - for $$$2$$$ minutes;  the $$$3$$$-rd singer in the $$$1$$$-st city will give a concert for $$$6$$$ minutes, in the $$$2$$$-nd — for $$$9$$$ minutes, in the $$$3$$$-rd — for $$$3$$$ minutes. 

Sample Inputs:
4
3
12 16 14
1
1
3
1 2 3
6
81 75 75 93 93 87

Sample Outputs:
YES
3 1 3 
YES
1 
NO
YES
5 5 4 1 4 5

Solution (Python):
for i in range(int(input())):
    n = int(input())
    b = list(map(int, input().split()))
    if n == 1:
        print('YES')
        print(b[0])
        continue
    S = sum(b)
    N = n * (n + 1)
    if 2 * S % N:
        print('NO')
        continue
    s = 2 * S // N
    a = []
    flag = True
    for i in range(n):
        x = s - b[i] + b[i - 1]
        if x % n != 0 or x <= 0:
            flag = False
            print('NO')
            break
        a.append(str(x // n))
    if flag:
        print('YES')
        print(' '.join(a))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def singer_tour(n, b):
    m = n * (n + 1) // 2
    sum_b = sum(b)
    sum_a = sum_b // m
    a = [0] * n
    if sum_b != sum_a * m:
        sys.stdout.write('NO\n')
        return
    if (b[0] - b[n - 1] - sum_a) % -n != 0:
        sys.stdout.write('NO\n')
        return
    a[0] = (b[0] - b[n - 1] - sum_a) // -n
    if a[0] < 1:
        sys.stdout.write('NO\n')
        return
    for i in range(1, n):
        if (b[i] - b[i - 1] - sum_a) % -n != 0:
            sys.stdout.write('NO\n')
            return
        a[i] = (b[i] - b[i - 1] - sum_a) // -n
        if a[i] < 1:
            sys.stdout.write('NO\n')
            return
    sys.stdout.write('YES\n')
    sys.stdout.write(f"{' '.join(map(str, a))}\n")
for _ in range(int(input())):
    n = int(input())
    b = list(map(int, input().split()))
    singer_tour(n, b)

Solution (Python):
for i in range(int(input())):
    n = int(input())
    b = list(map(int, input().split()))
    if n == 1:
        print('YES')
        print(b[0])
        continue
    S = sum(b)
    N = n * (n + 1)
    if 2 * S % N:
        print('NO')
        continue
    s = 2 * S // N
    a = []
    flag = True
    for i in range(n):
        x = s - b[i] + b[i - 1]
        if x % n != 0 or x <= 0:
            flag = False
            print('NO')
            break
        a.append(str(x // n))
    if flag:
        print('YES')
        print(' '.join(a))