Range = √Sum (Codeforces 1758D)
Tags: Math, two pointers

You are given an integer $$$n$$$. Find a sequence of $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ such that $$$1 \leq a_i \leq 10^9$$$ for all $$$i$$$ and $$$$$$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)= \sqrt{a_1 + a_2 + \dots + a_n}.$$$$$$It can be proven that there exists a sequence of distinct integers that satisfies all the conditions above.

Input: The first line of input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.The first and only line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the length of the sequence you have to find.The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, output $$$n$$$ space-separated distinct integers $$$a_1, a_2, \dots, a_n$$$ satisfying the conditions in the statement. If there are several possible answers, you can output any of them. Please remember that your integers must be distinct!

Note: In the first test case, the maximum is $$$3$$$, the minimum is $$$1$$$, the sum is $$$4$$$, and $$$3 - 1 = \sqrt{4}$$$.In the second test case, the maximum is $$$29$$$, the minimum is $$$18$$$, the sum is $$$121$$$, and $$$29-18 = \sqrt{121}$$$.For each test case, the integers are all distinct.

Sample Inputs:
3
2
5
4

Sample Outputs:
3 1
20 29 18 26 28
25 21 23 31

Solution (Python):
import math
for i in range(int(input())):
    n = int(input())
    res = []
    if not n & 1:
        for i in range(math.ceil(n / 2), 0, -1):
            res.append(n - i)
        for i in range(1, math.ceil(n / 2) + 1):
            res.append(n + i)
    else:
        for i in range(n - n // 2, n + n // 2 + 1):
            res.append(i)
        res[0] -= 1
        res[-1] += 1
        res[-2] += 1
        for i in range(len(res)):
            res[i] += 2
    print(' '.join(map(str, res)))

Solution (Python):
for t in range(int(input())):
    n = int(input())
    if n % 2 == 0:
        ans = list(range(int(n / 2), n)) + list(range(n + 1, int(3 * n / 2) + 1))
    else:
        ans = list(range(n - int(n / 2) + 2, n + int(n / 2) + 3))
        ans[0] -= 1
        ans[-1] += 1
        ans[-2] += 1
    print(' '.join([str(x) for x in ans]))

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        l = list(range(n - n // 2, n)) + list(range(n + 1, n + 1 + n // 2))
        print(' '.join([str(x) for x in l]))
    else:
        l = [4 * n, 3 * n, 5 * n]
        if n > 3:
            i = (n - 3) // 2
            l += list(range(4 * n - 1, 4 * n - i - 1, -1))
            l += list(range(4 * n + 1, 4 * n + i + 1))
        print(' '.join([str(x) for x in l]))