Header Ads Widget

Subarray permutations | codechef solution

Rajnish Tripathi 15:05

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: �[3…3]=[1], �[1…3] =[2,3,1], �[2…5]=[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

  • 1≤�≤103
  • 1≤�≤105
  • 1≤�≤�
  • Sum of � over all test cases does not exceed 3⋅105.

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 �[1…1].

Test case 2: The permutation [1,3,2] contains 2 good subsegments: �[1…1], �[1…3].

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: �[3…3],�[2…5],�[1…5]. 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:-








Tags:

Post a Comment

0 Comments