Max Pair Sums of 2 arrays

[vardhanrao]

Max Pair Sums of 2 arrays

Given 2 integer arrays - A & B, you can create new elements of the form : A[i] + B[j] where 0<=i,j<=N-1. You have to print the highest K elements of the newly created elements.

Input Format

First line of input contains T - number of test cases. Its followed by 3T lines -

1. The first line contains N: the size of the arrays and K: the number of elements to print.
2. The second line contains N integers - the elements of A.
3. The third line contains N integers - the elements of B.

Constraints

• 40 points

  • 1 <= T <= 100
  • 1 <= N <= 10²
  • 1 <= K <= min(10², N*N)
  • -104 <= A[i],B[i] <= 10⁴

• 60 points

  • 1 <= T <= 100
  • 1 <= N <= 10³
  • 1 <= K <= min(10³, N*N)
  • -104 <= A[i],B[i] <= 10⁴

• 100 points

  • 1 <= T <= 100
  • 1 <= N <= 10⁴
  • 1 <= K <= min(10⁴, N*N)
  • -104 <= A[i],B[i] <= 10⁴

Output Format

For each test case, print the highest K elements separated by space in a sorted order. Print new line between output of different test cases.

Sample Input 0

2
3 2
2 -5 14 
-12 5 -3 
5 5
-10 14 11 -5 12 
16 -10 -3 13 11 

Sample Output 0

19 11
30 28 27 27 25

Explanation 0

Test Case 1
You can form the following new elements:
2+(-12) = -10, 2+5 = 7, 2+(-3) = -1
(-5)+(-12) = -17, (-5)+5 = 0, (-5)+(-3) = -8
14+(-12) = 2, 14+5 = 19, 14+(-3) = 11
Top 2 elements = 19, 11

[devikasugathan]

Done in #22