Woeful Permutation
Contest: Codeforces Round 813 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, number theory

You 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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
2
1
2

Example output:
1 
2 1

Editorial:
A well know fact is that $$$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b$$$ for any two positive integers $$$a$$$ and $$$b$$$. Since $$$\gcd(x, x + 1) = 1$$$ for all positive $$$x$$$, we get that $$$\operatorname{lcm}(x,x+1) = x \cdot (x + 1)$$$.
All of this should hint that for even $$$n$$$, the optimal permutation looks like this: $$$2,1,4,3,\ldots,n,n-1$$$. Add for odd $$$n$$$, it looks like this: $$$1,3,2,5,4,\ldots,n,n-1$$$.
Complexity: $$$\mathcal{O}(n)$$$
Turns out the formal proof is pretty hard. You are welcome to try and find something simpler.
$$$ $$$
Define $$$f(x, y)$$$ as $$$x \cdot y$$$ if $$$x \ne y$$$, and $$$x$$$ otherwise. It is easy to see that $$$\operatorname{lcm}(x, y) \le f(x, y)$$$. We will find the maximum possible value of $$$f(1, p_1) + \ldots f(n, p_n)$$$ and show that it is reached by our construction.
Suppose we want to solve this problem: find the max possible value of $$$1 \cdot p_1 + \ldots + n \cdot p_n$$$, if for all $$$i > 1$$$, $$$p_i \ne i$$$. This is equivalent to maximizing $$$f(1, p_1) + \ldots f(n, p_n)$$$, because if there is such an index $$$i$$$, it is always optimal to swap $$$p_i$$$ with $$$p_j$$$ for any $$$1 \le j < i$$$.
Let's build a graph on this permutation with n vertices and add all edges $$$i \rightarrow p_i$$$. Except for maybe $$$p_1 = 1$$$, all the other cycles have a length of at least 2.
Let's look at one such cycle $$$x_1, x_2, \ldots, x_k$$$. The optimal value with no restrictions on the value of $$$p_i$$$ would be $$$x_1^2 + x_2^2 + \ldots + x_k^2$$$, but right now we have $$$x_1 \cdot x_2 + x_2 \cdot x_3 + \ldots + x_k \cdot x_1$$$. Subtracting one from the other:
$$$$$$x_1^2 + x_2^2 + \ldots + x_k^2 - (x_1 \cdot x_2 + x_2 \cdot x_3 + \ldots + x_k \cdot x_1) =$$$$$$ $$$$$$= \frac{x_1^2}{2} - x_1 \cdot x_2 + \frac{x_2^2}{2} + \frac{x_2^2}{2} - x_2 \cdot x_3 + \frac{x_3^2}{2} + \ldots + \frac{x_k^2}{2} - x_k \cdot x_1 + \frac{x_1^2}{2} =$$$$$$ $$$$$$= \frac{(x_1 - x_2)^2 + (x_2 - x_3)^2 + \ldots + (x_k - x_1)^2}{2} \ge$$$$$$ $$$$$$\ge \frac{|x_1 - x_2| + |x_2 - x_3| \ldots + |x_k - x_1|}{2} \ge$$$$$$ $$$$$$\ge \max(x_1 \ldots x_k) - \min(x_1 \ldots x_k)$$$$$$
So we need to minimize the sum of $$$\max(x_1 \ldots x_k) - \min(x_1 \ldots x_k)$$$ over all cycles.
If $$$n$$$ is even, it is easy to see the minimum possible value of this is $$$\frac{n}{2}$$$, and it doesn't matter what $$$p_1$$$ equals to.
For odd $$$n$$$ we have to look at two cases: $$$p_1 = 1$$$ and $$$p_1 \ne 1$$$. In the first case, the minimum possible sum is $$$\frac{n - 1}{2}$$$, in the second case, it is $$$\frac{n + 1}{2}$$$, which is worse that in the previous case.
Returning to the original problem, our constructions also achieve this minimal difference from $$$1^2 + 2^2 + \ldots n$$$ even when we change $$$f$$$ back into $$$\operatorname{lcm}$$$, so they are optimal.