Permutations & Primes (Codeforces 1844B)
Tags: Math, constructive algorithms

You are given a positive integer $$$n$$$.In this problem, the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\dots,c_k$$$ is defined as the smallest positive integer $$$x$$$ which does not occur in the collection $$$c$$$. The primality of an array $$$a_1,\dots,a_n$$$ is defined as the number of pairs $$$(l,r)$$$ such that $$$1 \le l \le r \le n$$$ and $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ is a prime number. Find any permutation of $$$1,2,\dots,n$$$ with the maximum possible primality among all permutations of $$$1,2,\dots,n$$$. Note:   A prime number is a number greater than or equal to $$$2$$$ that is not divisible by any positive integer except $$$1$$$ and itself. For example, $$$2,5,13$$$ are prime numbers, but $$$1$$$ and $$$6$$$ are not prime numbers.  A permutation of $$$1,2,\dots,n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). 

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

Output: For each test case, output $$$n$$$ integers: a permutation of $$$1,2,\dots,n$$$ that achieves the maximum possible primality.If there are multiple solutions, print any of them.

Note: In the first test case, there are $$$3$$$ pairs $$$(l,r)$$$ with $$$1 \le l \le r \le 2$$$, out of which $$$2$$$ have a prime $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:   $$$(l,r) = (1,1)$$$: $$$\operatorname{MEX}(2) = 1$$$, which is not prime.  $$$(l,r) = (1,2)$$$: $$$\operatorname{MEX}(2,1) = 3$$$, which is prime.  $$$(l,r) = (2,2)$$$: $$$\operatorname{MEX}(1) = 2$$$, which is prime.  Therefore, the primality is $$$2$$$.In the second test case, $$$\operatorname{MEX}(1) = 2$$$ is prime, so the primality is $$$1$$$.In the third test case, the maximum possible primality is $$$8$$$.

Sample Inputs:
3
2
1
5

Sample Outputs:
2 1
1
5 2 1 4 3

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = [str(i + 1) for i in range(n)]
    if n >= 3:
        (a[2], a[-1]) = (a[-1], a[2])
        (a[0], a[1]) = (a[1], a[0])
    if n >= 2:
        (a[1], a[n // 2]) = (a[n // 2], a[1])
    print(' '.join(a))

Solution (Python):
import sys
for line in sys.stdin:
    n = int(line.strip())
    for i in range(n):
        te = int(sys.stdin.readline().strip())
        v = [0] * te
        v[0] = 2
        v[-1] = 3
        v[te // 2] = 1
        count = 4
        for j in range(1, te - 1):
            if j == te // 2:
                continue
            v[j] = count
            count += 1
        print(' '.join(map(str, v)))

Solution (Python):
import bisect
import collections
import heapq
import math
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)

def solve():
    n = ii()
    if n == 1:
        return 1
    if n == 2:
        return '2 1'
    if n == 3:
        return '3 1 2'
    ans = '2 '
    for i in range(4, 4 + (n - 3) // 2):
        ans += f'{i} '
    ans += '1 '
    for i in range(4 + (n - 3) // 2, n + 1):
        ans += f'{i} '
    return ans + '3'

def main():
    for _ in range(ii()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()