# Subarray permutations | codechef solution

## Problem:-

A permutation of length $�$ is an array of $�$ integers $�=\left[{�}_{1},{�}_{2},\dots ,{�}_{�}\right]$ such that every integer from $1$ to $�$ (inclusive) appears in it exactly once. For example, $\left[2,3,4,1\right]$ is a permutation of length $4$.

A subsegment of an array $�\left[�\dots �\right]=\left[{�}_{�},{�}_{�+1},\dots ,{�}_{�}$] is called good if the subsegment is a permutation of length $\left(�-�+1\right)$. For example, the array $�=\left[2,3,1,4,2\right]$ contains $3$ good subsegments: $�\left[3\dots 3\right]=\left[1\right],$ $�\left[1\dots 3\right]$ $=\left[2,3,1\right],$ $�\left[2\dots 5\right]=\left[3,1,4,2\right]$.

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

### Input Format

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

### Output Format

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

• If no permutation satisfies the given conditions, print −1.
• Otherwise, print $�$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$, denoting the elements of the permutation. If there are multiple answers, you can output any of them.

### Constraints

• $1\le �\le 1{0}^{3}$
• $1\le �\le 1{0}^{5}$
• $1\le �\le �$
• Sum of $�$ over all test cases does not exceed $3\cdot 1{0}^{5}$.

• Subtask 1 (100 points): Original constraints

### Sample 1:

Input
Output
4
1 1
3 2
4 1
5 3

1
1 3 2
-1
5 3 1 4 2


### Explanation:

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

Test case $2$: The permutation $\left[1,3,2\right]$ contains $2$ good subsegments: $�\left[1\dots 1\right]$$�\left[1\dots 3\right]$.

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

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

### Code(c++):-

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n,b;
cin>>n>>b;
if(b==1 and n!=1){
cout<<-1<<endl;
} else {
for(int i=0;i<b-1;i++){
cout<<i+1<<" ";
}
for(int i=n;i>=b;i--){
cout<<i<<" ";
}
cout<<endl;
}
}
return 0;
}

Code(java);-

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t;
t=sc.nextInt();
while(t!=0)
{
int n,a,b;
n=sc.nextInt();
a=sc.nextInt();
b=sc.nextInt();
int e,bob=0,alice=0,both=0;
for(int i=0;i<n;i++)
{
e=sc.nextInt();
if(e%a==0 && e%b==0)
both++;
else if(e%a==0)
bob++;
else if(e%b==0)
alice++;
}
if(both>0)
bob++;
if(bob>alice)
System.out.println("BOB");
else
System.out.println("ALICE");
t--;

}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-