Woeful Permutation (Codeforces 1712B)
Tags: Greedy, number theory

I wonder, does the falling rain Forever yearn for it's disdain?Effluvium of the MindYou are given a positive integer $$$n$$$.Find any permutation $$$p$$$ of length $$$n$$$ such that the sum $$$\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)$$$ is as large as possible. Here $$$\operatorname{lcm}(x, y)$$$ denotes the least common multiple (LCM) of integers $$$x$$$ and $$$y$$$.A permutation 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 1\,000$$$). Description of the test cases follows.The only line for each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ — the permutation with the maximum possible value of $$$\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)$$$.If there are multiple answers, print any of them.

Note: For $$$n = 1$$$, there is only one permutation, so the answer is $$$[1]$$$.For $$$n = 2$$$, there are two permutations:   $$$[1, 2]$$$ — the sum is $$$\operatorname{lcm}(1,1) + \operatorname{lcm}(2, 2) = 1 + 2 = 3$$$.  $$$[2, 1]$$$ — the sum is $$$\operatorname{lcm}(1,2) + \operatorname{lcm}(2, 1) = 2 + 2 = 4$$$. 

Sample Inputs:
2
1
2

Sample Outputs:
1 
2 1

Solution (Python):
def i():
    n = int(input())
    if n % 2:
        c = ['1']
        tp = 2
    else:
        c = []
        tp = 1
    for x in range(tp, n + 1, 2):
        c.append(f'{x + 1} {x}')
    return ' '.join(c)
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 == 1:
        print(f"1 {' '.join((f'{k + 1} {k}' for k in range(2, n + 1, 2)))}")
    else:
        print(f"{' '.join((f'{k + 1} {k}' for k in range(1, n + 1, 2)))}")

Solution (Python):
from itertools import permutations
import math

def lcm(o, u):
    return o * u / math.gcd(o, u)

def lcm_sum(z):
    return sum([lcm(i + 1, x) for (i, x) in enumerate(z)])

def lcm_tuple(z):
    return [lcm(i + 1, x) for (i, x) in enumerate(z)]

def main_0():
    best = None
    for z in permutations(range(1, int(input()) + 1)):
        z_sum = lcm_sum(p)
        if best == None or z_sum > best[1]:
            best = (z, z_sum)
    print(' '.join(map(str, best[0])))

def main():
    z = list(range(1, int(input()) + 1))
    for i in range(len(z) - 2, -1, -2):
        cur = z[i]
        z[i] = z[i + 1]
        z[i + 1] = cur
    print(' '.join(map(str, z)))
for _ in range(int(input())):
    main()