PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given an array A.
Find any pair of elements A_i, A_j such that A_i + A_j is not present in A, or claim that no such pair exists.
It’s allowed to choose the same element twice.
EXPLANATION:
The key behind solving this problem is to realize that if we’re able to create values that are very large or very small, we’ll be done.
In particular, let \text{mx} denote the maximum element of A.
Suppose \text{mx} \gt 0.
Then, observe that we can just choose \text{mx} twice, to obtain a sum of 2\cdot \text{mx}.
This value is definitely greater than anything present in A.
Ok, now what if \text{mx} \leq 0?
Let’s go the opposite direction: let \text{mn} denote the minimum element of A.
If \text{mn} \lt 0, then once again we can just take \text{mn} twice and obtain a sum of 2\cdot\text{mn}, which is smaller than anything in A.
What if both above checks fail?
That would mean we have \text{mx} \leq 0 and \text{mn} \geq 0.
However, this is only possible if every element of A is 0.
But, if this is the case, then the sum of any two elements will also be 0 (and hence present in A), so no solution exists in this case.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if max(a) > 0: print(max(a), max(a))
elif min(a) < 0: print(min(a), min(a))
else: print(-1)