Header Ads Widget

Subarray permutations | codechef solution

Problem:-

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

A subsegment of an array []=[,+1,,] is called good if the subsegment is a permutation of length (+1). For example, the array =[2,3,1,4,2] contains 3 good subsegments: [33]=[1], [13] =[2,3,1], [25]=[3,1,4,2].

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,,, denoting the elements of the permutation. If there are multiple answers, you can output any of them.

Constraints

  • 1103
  • 1105
  • 1
  • Sum of  over all test cases does not exceed 3105.

Subtasks

  • 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 [1], which contains one good subsegment [11].

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

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

Test case 4: The permutation [5,3,1,4,2] contains 3 good subsegments: [33],[25],[15]. 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;
}
}
    // your code goes here
    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
  {
    // your code goes here
    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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-