[Solution] Average Permutation CodeChef Solution

Problem

You are given an integer $N$.

Find a permutation $P = [P_1, P_2, \ldots, P_N]$ of the integers $\{1, 2, \ldots, N\}$ such that sum of averages of all consecutive triplets is minimized, i.e.

$$\sum_{i=1}^{N-2} \frac{P_i + P_{i+1} + P_{i+2}}{3}$$

is minimized.

If multiple permutations are possible, print any of them.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• The first and only line of each test case contains an integer N, the size of the permutation.

Output Format

For each test case, output on a new line a permutation which satisfies the above conditions.

Explanation:

Test case $1$: The sum is $\frac{P_1 + P_2 + P_3}{3} + \frac{P_2 + P_3 + P_4}{3} = \frac{3 + 2 + 1}{3} + \frac{2 + 1 + 4}{3} = 6/3 + 7/3 = 4.333\ldots$ Among all possible permutations of $\{1, 2, 3, 4\}$, this is one of the permutations which provides the minimum result.

Test case $2$: The sum is $\frac{3+2+1}{3} = 6/3 = 2$. Every permutation of size $3$ will have this value, hence it is the minimum possible.