[Solution] Perfect Permutation solution codeforces – Find a permutation 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn with the minimum possible weight (among all permutations of length 𝑛n).

Perfect Permutation solution codeforces – You are given a positive integer 𝑛n.

The weight of a permutation 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn is the number of indices 1𝑖𝑛1≤i≤n such that 𝑖i divides 𝑝𝑖pi. Find a permutation 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn with the minimum possible weight (among all permutations of length 𝑛n).

A permutation is an array consisting of 𝑛n distinct integers from 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).

[Solution] Perfect Permutation solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). The description of the test cases follows.

The only line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105) — the length of permutation.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.


For each test case, print a line containing 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn so that the permutation 𝑝p has the minimum possible weight.

If there are several possible answers, you can print any of them.

[Solution] Perfect Permutation solution codeforces



2 1 4 3

[Solution] Perfect Permutation solution codeforces

In the first test case, the only valid permutation is 𝑝=[1]p=[1]. Its weight is 11.

In the second test case, one possible answer is the permutation 𝑝=[2,1,4,3]p=[2,1,4,3]. One can check that 11 divides 𝑝1p1 and 𝑖i does not divide 𝑝𝑖pi for 𝑖=2,3,4i=2,3,4, so the weight of this permutation is 11. It is impossible to find a permutation of length 44 with a strictly smaller weight.


For Solution

Click Here

Leave a Comment