[Solution] Average Permutation solution codechef

Average Permutation solution codechef – 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.

Table of Contents

[Solution] Average Permutation solution codechef

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

Average Permutation solution codechef

  • 1 \leq T \leq 1000
  • 3 \leq N \leq 10^5
  • The sum of N over all test cases won’t exceed 3\cdot 10^5.

Sample 1:

Input

Output

2
4
3
3 2 1 4
3 2 1

Average Permutation solution codechef 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.

For Solution

Click Here

Leave a Comment