PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given an array A, find whether it has 4 indices 1 \leq i \lt j \lt k \lt l \leq N such that A_i+A_j \neq A_k + A_l.
EXPLANATION:
If N = 4, we have no choice: there’s only one choice of 4 indices, so the answer is Yes
if A_1+A_2\neq A_3+A_4 and No
otherwise.
If N\geq 5 we have a bit more freedom in our choice of four indices, which ends up being a lot: it turns out that the answer is No
if and only if all the elements of A are the same!
Proof
If all the elements of A are the same, then the answer is obviously No
since any pair of elements will have the same sum.
Conversely, suppose the answer is No
.
Consider N = 5.
Then, we know that A_1 + A_2 = A_3 + A_4 = A_3 + A_5 = A_4 + A_5; so all three of A_3,A_4,A_5 must be equal.
Similarly, A_1+A_2=A_1+A_3=A_1+A_2, all being equal to A_4+A_5.
So all three of A_1,A_2,A_3 must be equal; which along with the previous conclusion means that all five elements must be equal.
For N\gt 5, simply apply this argument to each subarray of length 5 to see that all the elements must be equal, as claimed.
So, when N\geq 5, just check if all the elements are equal and print Yes
or No
appropriately.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if n == 4: print('Yes' if a[0] + a[1] != a[2] + a[3] else 'No')
else: print('Yes' if min(a) < max(a) else 'No')