Fixed number of Fixed Points solution codechef

• For Solution

  Click Here!

Given a positive integer nn and an integer kk such that 0≤k≤n0≤k≤n, find any permutation AA of 1,2…n1,2…n such that the number of indices for which Ai=iAi=i is exactly kk. If there exists no such permutation, print −1−1. If there exist multiple such permutations, print any one of them.

Fixed number of Fixed Points solution codechef

• First line of the input contains TT, the number of test cases. Then the test cases follow.
• Each test case contains a single line of input, two integers n,kn,k.

Output Format

For each test case, print a permutation in a single line, if a permutation with the given constraints exists. Print −1−1 otherwise.

Constraints

• 1≤T≤1051≤T≤105
• 1≤n≤1051≤n≤105
• 0≤k≤n0≤k≤n
• Sum of nn over all test cases doesn’t exceed 2⋅1062⋅106

Fixed number of Fixed Points solution codechef

 

3
2 1
3 1
4 2

Fixed number of Fixed Points solution codechef

 

-1
1 3 2
3 2 1 4

Fixed number of Fixed Points solution codechef

Test case 11: There are total 22 permutations of [1,2][1,2] which are [1,2][1,2] and [2,1][2,1]. There are 22 indices in [1,2][1,2] and 00 indices in [2,1][2,1] for which Ai=iAi=i holds true. Thus, there doesn’t exist any permutation of [1,2][1,2] with exactly 11 index ii for which Ai=iAi=i holds true.

Test case 22: Consider the permutation A=[1,3,2]A=[1,3,2]. We have A1=1A1=1, A2=3A2=3 and A3=2A3=2. So, this permutation has exactly 11 index such that Ai=iAi=i.

• For Solution

  Click Here!