Subarray permutations solution|Codesheff lunchtime 2022 for div 3

A permutation of length N$N$ is an array of N$N$ integers P=[P1,P2,…,PN]$P=[P_1,P_2,\dots ,P_N]$ such that every integer from 1$1$ to N$N$ (inclusive) appears in it exactly once. For example, [2,3,4,1]$[2,3,4,1]$ is a permutation of length 4$4$.

A subsegment of an array A[L…R]=[AL,AL+1,…,AR$A[L\dots R]=[A_L,A_{L+1},\dots ,A_R$] 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 3$3$ good subsegments: A[3…3]=[1],$A[3\dots 3]=[1],$ A[1…3]$A[1\dots 3]$ =[2,3,1],$=[2,3,1],$ A[2…5]=[3,1,4,2]$A[2\dots 5]=[3,1,4,2]$.

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

Input Format

• The first line contains an integer T$T$, denoting the number of test cases. The T$T$ test cases then follow:
• The first and only line of each test case contains two space-separated integers N,K$N,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 N$N$ space-separated integers P1,P2,…,PN$P_1,P_2,\dots ,P_N$, denoting the elements of the permutation. If there are multiple answers, you can output any of them.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤K≤N$1\le K\le N$
• Sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$.

Subtasks

• Subtask 1 (100 points): Original constraints

Sample Input 1 

4
1 1
3 2
4 1
5 3

Sample Output 1 

1
1 3 2 
-1
5 3 1 4 2

Explanation

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

Test case 2$2$: The permutation [1,3,2]$[1,3,2]$ contains 2$2$ good subsegments: A[1…1]$A[1\dots 1]$, A[1…3]$A[1\dots 3]$.

Test case 3$3$: There is no way to construct a permutation of length 4$4$ which contains one good subsegment.

Test case 4$4$: The permutation [5,3,1,4,2]$[5,3,1,4,2]$ contains 3$3$ good subsegments: A[3…3],A[2…5],A[1…5]$A[3\dots 3],A[2\dots 5],A[1\dots 5]$. There are other permutations of length 5$5$ having 3$3$ good subsegments.

Solution:

This question solution is updated within contest time. please click on follow button and subscribe our channel.if you follow and subscribe our channel then get notification of answer as soon as possible.