average permutation

Try solving this problem statement on your own first and then try to understand the code, followed by the explanation :) 

You are given an integer 

$�$.

Find a permutation $�=[{�}_1,{�}_2,\dots ,{�}_{�}]$ of the integers $\{1,2,\dots ,�\}$ such that sum of averages of all consecutive triplets is minimized, i.e.

$$\sum _{�=1}^{�-2}\frac{{�}_{�}+{�}_{�+1}+{�}_{�+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 $�$, 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.

Constraints

• $1\le �\le 1000$
• $3\le �\le 10^5$
• The sum of $�$ 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

Explanation:

Test case $1$: The sum is $\frac{{�}_1+{�}_2+{�}_3}{3}+\frac{{�}_2+{�}_3+{�}_4}{3}=\frac{3+2+1}{3}+\frac{2+1+4}{3}=6\mathrm{/}3+7\mathrm{/}3=4.333\dots$ 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\mathrm{/}3=2$. Every permutation of size $3$ will have this value, hence it is the minimum possible.

Python Code:

for _ in range(int(input())):

    n=int(input())

    ans=[0]*n

    itr=0

    for i in range(n,0,-2):

        ans[itr]=i

        if(i!=1):

            ans[n-1-itr]=i-1

        itr+=1

    print(*ans,sep=" ")

Explanation:- 

Basically, in this problem, the main part is that we need to decrease the summation of the averages of every 3 consecutive numbers.

Now, let's break this problem, to decrease the summation of averages, we need to decrease every average itself, right? Now how are we going to decrease that average? So every average will consist of 3 numbers, and we know what is the formula for average, summation of nums/no. of numbers, now we just need to decrease this fraction. This is called break and solve technique...maybe, I am not sure what this might be called cz I have just learned this myself. So, coming back to the problem, we need to decrease the fraction, so we need to decrease the numerator, that is summation of the 3 numbers, now to decrease the summation of the 3 numbers, we need to have smaller numbers, but the problem is that even if we take smaller numbers, then also bigger numbers will come into play now or later, right? 

Yes, they(bigger numbers) will have to be included, but what if we can decrease the number of occurrences of bigger numbers. If you will imagine, then you will understand that when we take 3 numbers consecutively, then most outer nums are included just once, then inner nums are included 2 times, then the most inner nums are included 3 times( try this for an array of size 5, start piking consecutive 3 nums ), means we get to the conclusion that the outermost nums come the least number of times, so their role in the summation would be less and we want that only right? We want the biggest nums to be as less included in the summation as possible. 

So now, we cracked the idea, and we just need to start accessing the biggest elems, means access in Descending order, and start keeping the nums, in the first and last positions and then going inner in the array respectively.

The top 2 biggest nums will be in 2 outermost sides of the array(or we can say the permutation).

Then the next inner extremes will contain the next biggest nums, and so on, like we check  a Palindrome string, the looping will be just like that.