Build Permutation (Codeforces 1713C)
Tags: Math, dp

A $$$\mathbf{0}$$$-indexed array $$$a$$$ of size $$$n$$$ is called good if for all valid indices $$$i$$$ ($$$0 \le i \le n-1$$$), $$$a_i + i$$$ is a perfect square$$$^\dagger$$$.Given an integer $$$n$$$. Find a permutation$$$^\ddagger$$$ $$$p$$$ of $$$[0,1,2,\ldots,n-1]$$$ that is good or determine that no such permutation exists.$$$^\dagger$$$ An integer $$$x$$$ is said to be a perfect square if there exists an integer $$$y$$$ such that $$$x = y^2$$$.$$$^\ddagger$$$ An array $$$b$$$ is a permutation of an array $$$a$$$ if $$$b$$$ consists of the elements of $$$a$$$ in arbitrary order. For example, $$$[4,2,3,4]$$$ is a permutation of $$$[3,2,4,4]$$$ while $$$[1,2,2]$$$ is not a permutation of $$$[1,2,3]$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output $$$n$$$ distinct integers $$$p_0, p_1, \dots, p_{n-1}$$$ ($$$0 \le p_i \le n-1$$$) — the permutation $$$p$$$ — if the answer exists, and $$$-1$$$ otherwise.

Note: In the first test case, we have $$$n=3$$$. The array $$$p = [1, 0, 2]$$$ is good since $$$1 + 0 = 1^2$$$, $$$0 + 1 = 1^2$$$, and $$$2 + 2 = 2^2$$$In the second test case, we have $$$n=4$$$. The array $$$p = [0, 3, 2, 1]$$$ is good since $$$0 + 0 = 0^2$$$, $$$3 + 1 = 2^2$$$, $$$2+2 = 2^2$$$, and $$$1+3 = 2^2$$$.

Sample Inputs:
3
3
4
7

Sample Outputs:
1 0 2 
0 3 2 1 
1 0 2 6 5 4 3

Solution (Python):
import sys, math
INPUT = sys.stdin.readline

def ii():
    return int(INPUT())

def iit(strip=False):
    s = INPUT().strip('[]\n').split(',') if strip else INPUT().split()
    return map(int, s)

def iil(strip=False):
    s = INPUT().strip('[]\n').split(',') if strip else INPUT().split()
    return list(map(int, s))

def si():
    return INPUT()[:-1]

def rec(n):
    m = n - 1
    ma = int(math.sqrt(m))
    if ma ** 2 == m:
        return list(reversed(range(n)))
    mb = ma + 1
    nn = mb ** 2 - m
    return rec(nn) + list(reversed(range(nn, n)))

def solve():
    n = ii()
    r = rec(n)
    print(' '.join([str(x) for x in r]))
CASES = True
FROM_FILE = False
if FROM_FILE:
    FILE = open('input.txt', 'r')
    INPUT = FILE.readline
if CASES:
    t = ii()
    for i in range(t):
        solve()
else:
    solve()
if FROM_FILE:
    FILE.close()

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

def solution(n):
    current = n - 1
    r = int(current ** 0.5)
    if r ** 2 < current:
        r += 1
    first = r ** 2 - current
    if first == 0:
        return list(range(n))
    return list(range(first, n)) + solution(first)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n = int(input())
        result = solution(n)
        print(' '.join(map(str, result[::-1])))

Solution (Python):
import math
import sys
MAXN = int(100000.0) + 1
res = [-1] * MAXN
res[0] = ''
res[1] = '0'

def solve(n):
    if res[n] != -1:
        return res[n]
    return solve(math.ceil(math.sqrt(n - 1)) ** 2 - n + 1) + ' ' + ' '.join([str(i) for i in range(n - 1, math.ceil(math.sqrt(n - 1)) ** 2 - n, -1)])
t = int(input())
for _ in range(t):
    print(solve(int(input())).strip(' '))