Question Name:PERMUTING TWO ARRAYS

#include<bits/stdc++.h> 
using namespace std; 
  
 
bool isPossible(int a[], int b[], int n, int k) 
{ 
    sort(a, a + n); 
  
    sort(b, b + n, greater<int>()); 
  
    for (int i = 0; i < n; i++) 
        if (a[i] + b[i] < k) 
            return false; 
  
    return true; 
} 
  
int main() 
{ 

    int k,i,j,q; 
    int n;
cin>>j;
  for(q=0;q<j;q++) { cin>>n>>k;  int a[n],b[n];

  for(i=0;i<n;i++) { 
    cin>>a[i];} 
  for(i=0;i<n;i++) { 
    cin>>b[i];} 
  
    isPossible(a, b, n, k) ? cout << "YES" : 
                             cout << "NO"; 
                   cout<<endl;}
    return 0; 
} 
  • Problem Description
    Consider two n-element arrays of integers, A=[a0,a1,…,an-1] and B=[b0,b1,…,bn-1]. You want to permute them into some A’ and B’ such that the relation ai’+bi’>=k holds for all i where 0<=i<=n. For example, if A=[0,1] B=[0,2] , and k=1, a valid A’, B’ satisfying our relation would be A’=[1,0] and B’=[0,2].

    You are given q queries consisting of A,B and k. For each query, print YES on a new line if some permutations A’, B’ exist satisfying the relation above. If no valid permutations exist, print NO instead.

    Input Format

    The first line contains an integer, q, denoting the number of queries. The 3q subsequent lines describe each of the q queries in the following format:

    1.The first line contains two space-separated integers describing the respective values of n(the size of arraysA and B) and k (the relation variable).
    2. The second line contains n space-separated integers describing the respective elements of array A.
    3.The third line contains n space-separated integers describing the respective elements of array B.

    Constraints
    1<=q<=10 
    1<=n<=1000 
    1<=k<=10^9 
    0<=ai, bi<=10^9

    Output Format

    For each query, print YES on a new line if valid permutations exist; otherwise, print NO.
  • Test Case 1
    Input (stdin)2
    3 10
    2 1 3
    7 8 9
    4 5
    1 2 2 1
    3 3 3 4
    Expected OutputYES
    NO
  • Test Case 2
    Input (stdin)2
    4 5
    1 2 2 1
    3 3 3 4
    3 10
    2 1 3
    7 8 9
    Expected OutputNO
    YES

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.