Permuting Two Arrays
Problem Statement :
There are two -element arrays of integers, and . Permute them into some and such that the relation holds for all where . There will be queries consisting of , , and . For each query, return YES if some permutation , satisfying the relation exists. Otherwise, return NO. A valid is and : and . Return YES. Function Description Complete the twoArrays function in the editor below. It should return a string, either YES or NO. twoArrays has the following parameter(s): int k: an integer int A[n]: an array of integers int B[n]: an array of integers Returns - string: either YES or NO Input Format The first line contains an integer , the number of queries. The next sets of lines are as follows: The first line contains two space-separated integers and , the size of both arrays and , and the relation variable. The second line contains space-separated integers . The third line contains space-separated integers .
Solution :
Solution in C :
In C :
#include<stdio.h>
void sort(long long int x[],int first,int last){
long long int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
sort(x,first,j-1);
sort(x,j+1,last);
}
}
main()
{
long long int a[1000],b[1000],i,j,k,flag,n,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&k);
for(i=0;i<n;++i)
scanf("%lld",&a[i]);
for(i=0;i<n;++i)
scanf("%lld",&b[i]);
sort(a,0,n-1);
sort(b,0,n-1);
flag=1;
for(i=0;i<n;++i)
{
if((a[i]+b[n-1-i])<k)
{
flag=0;
break;
}
}
if(flag==1)
printf("YES\n");
else
printf("NO\n");
}
}
Solution in C++ :
In C++ :
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int A[1005], B[1005];
int main() {
int T;
scanf("%d", &T);
while(T--){
int N, K;
scanf("%d%d", &N, &K);
for(int i=0; i < N; ++i)
scanf("%d", A+i);
for(int i=0; i < N; ++i)
scanf("%d", B+i);
sort(A, A+N);
sort(B, B+N);
bool ok=1;
for(int i=0; i < N; ++i)
if(A[i]+B[N-1-i] < K)
ok=0;
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
Solution in Java :
In Java :
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.util.Arrays.*;
public class Solution {
private static final int mod = (int)1e9+7;
final Random random = new Random(1);
final IOFast io = new IOFast();
public void run() throws IOException {
int T = io.nextInt();
LOOP: while(T-- != 0) {
int n = io.nextInt();
int k = io.nextInt();
int[] A = new int[n];
int[] B = new int[n];
for(int i = 0; i < A.length; i++) {
A[i] = io.nextInt();
}
for(int i = 0; i < A.length; i++) {
B[i] = io.nextInt();
}
sort(A);
sort(B);
for(int i = 0; i < A.length; i++) {
if(A[i] + B[n-1-i] < k) {
io.out.println("NO");
continue LOOP;
}
}
io.out.println("YES");
}
}
void main() throws IOException {
// IOFast.setFileIO("rle-size.in", "rle-size.out");
try {
run();
}
catch (EndOfFileRuntimeException e) { }
io.out.flush();
}
public static void main(String[] args) throws IOException {
new Solution().main();
}
static class EndOfFileRuntimeException extends RuntimeException {
private static final long serialVersionUID = -8565341110209207657L; }
static
public class IOFast {
private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
private PrintWriter out = new PrintWriter(System.out);
void setFileIO(String ins, String outs) throws IOException {
in = new BufferedReader(new FileReader(ins));
out = new PrintWriter(new FileWriter(outs));
}
// private static final int BUFFER_SIZE = 50 * 200000;
private static int pos, readLen;
private static final char[] buffer = new char[1024 * 8];
private static final char[] str = new char[500000*8*2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static {
for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; }
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}
public int read() throws IOException {
if(pos >= readLen) {
pos = 0;
readLen = in.read(buffer);
if(readLen <= 0) { throw new EndOfFileRuntimeException(); }
}
return buffer[pos++];
}
public int nextInt() throws IOException {
return Integer.parseInt(nextString());
}
public long nextLong() throws IOException {
return Long.parseLong(nextString());
}
public char nextChar() throws IOException {
while(true) {
final int c = read();
if(!isSpace[c]) { return (char)c; }
}
}
int reads(char[] cs, int len, boolean[] accept) throws IOException {
try {
while(true) {
final int c = read();
if(accept[c]) { break; }
str[len++] = (char)c;
}
}
catch(EndOfFileRuntimeException e) { ; }
return len;
}
public char[] nextLine() throws IOException {
int len = 0;
str[len++] = nextChar();
len = reads(str, len, isLineSep);
try {
if(str[len-1] == '\r') { len--; read(); }
}
catch(EndOfFileRuntimeException e) { ; }
return Arrays.copyOf(str, len);
}
public String nextString() throws IOException {
return new String(next());
}
public char[] next() throws IOException {
int len = 0;
str[len++] = nextChar();
len = reads(str, len, isSpace);
return Arrays.copyOf(str, len);
}
public double nextDouble() throws IOException {
return Double.parseDouble(nextString());
}
}
}
Solution in Python :
In Python3 :
def isGood(listA, listB, k):
n = len(listA)
listA.sort()
listB.sort(reverse=True)
for i in range(n):
if listA[i]+listB[i] < k:
return False
return True
T = int(input().strip())
for i in range(T):
[n, k] = [int(x) for x in input().strip().split()]
listA = [int(x) for x in input().strip().split()]
listB = [int(x) for x in input().strip().split()]
if isGood(listA, listB, k):
print("YES")
else:
print("NO")
View More Similar Problems
2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →