Fixed number of Fixed Points solution codechef

Fixed number of Fixed Points solution codechef

Given a positive integer nn and an integer kk such that 0kn0≤k≤n, find any permutation AA of 1,2n1,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

  • 1T1051≤T≤105
  • 1n1051≤n≤105
  • 0kn0≤k≤n
  • Sum of nn over all test cases doesn’t exceed 21062⋅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=1A2=3A2=3 and A3=2A3=2. So, this permutation has exactly 11 index such that Ai=iAi=i.

Leave a Comment