Subarray permutations solution codechef- A permutation of length NN is an array of NN integers P=[P1,P2,…,PN]P=[P1,P2,…,PN] such that every integer from 11 to NN (inclusive) appears in it exactly once. For example, [2,3,4,1][2,3,4,1] is a permutation of length 44. A subsegment of an array A[L…R]=[AL,AL+1,…,ARA[L…R]=[AL,AL+1,…,AR] is called good if the subsegment is a permutation of length (R−L+1)(R−L+1). For example, the array A=[2,3,1,4,2]A=[2,3,1,4,2] contains 33 good subsegments: A[3…3]=[1],A[3…3]=[1], A[1…3]A[1…3] =[2,3,1],=[2,3,1], A[2…5]=[3,1,4,2]A[2…5]=[3,1,4,2]. You are given two integers NN and KK. Find a permutation of length NN such that it contains exactly KK good subsegments. Print -1 if no such permutation exists.

Subarray permutations solution codechef

A permutation of length NN is an array of NN integers P=[P1,P2,,PN]P=[P1,P2,…,PN] such that every integer from 11 to NN (inclusive) appears in it exactly once. For example, [2,3,4,1][2,3,4,1] is a permutation of length 44.

A subsegment of an array A[LR]=[AL,AL+1,,ARA[L…R]=[AL,AL+1,…,AR] is called good if the subsegment is a permutation of length (RL+1)(R−L+1). For example, the array A=[2,3,1,4,2]A=[2,3,1,4,2] contains 33 good subsegments: A[33]=[1],A[3…3]=[1], A[13]A[1…3] =[2,3,1],=[2,3,1], A[25]=[3,1,4,2]A[2…5]=[3,1,4,2].

You are given two integers NN and KK. Find a permutation of length NN such that it contains exactly KK good subsegments. Print -1 if no such permutation exists.

Input Format Subarray permutations solution codechef

  • The first line contains an integer TT, denoting the number of test cases. The TT test cases then follow:
  • The first and only line of each test case contains two space-separated integers N,KN,K.

Output Format

For each test case, output a single line containing the answer:

  • If no permutation satisfies the given conditions, print −1.
  • Otherwise, print NN space-separated integers P1,P2,,PNP1,P2,…,PN, denoting the elements of the permutation. If there are multiple answers, you can output any of them.

Constraints Subarray permutations solution codechef

  • 1T1031≤T≤103
  • 1N1051≤N≤105
  • 1KN1≤K≤N
  • Sum of NN over all test cases does not exceed 31053⋅105.

Subtasks

  • Subtask 1 (100 points): Original constraints

Sample Input 1 

4
1 1
3 2
4 1
5 3

Sample Output 1  Subarray permutations solution codechef

1
1 3 2 
-1
5 3 1 4 2

Explanation

Test case 11: The only permutation of length 11 is [1][1], which contains one good subsegment A[11]A[1…1].

Test case 22: The permutation [1,3,2][1,3,2] contains 22 good subsegments: A[11]A[1…1]A[13]A[1…3].

Test case 33: There is no way to construct a permutation of length 44 which contains one good subsegment.

Test case 44: The permutation [5,3,1,4,2][5,3,1,4,2] contains 33 good subsegments: A[33],A[25],A[15]A[3…3],A[2…5],A[1…5]. There are other permutations of length 55 having 33 good subsegments.

Leave a Comment

Your email address will not be published.