SUMNEQ7 - Editorial

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')
1 Like

Can someone please explain this part in more detail how this expression is valid A1+ A2 = A1 + A3 = A1 + A2, given 1<=i<j<k<l<=N

And also, how we reach to this conclusion A1 = A2 = A3?

Thanks.

Remember that I said this for the case when the answer is No, i.e, for any i\lt j\lt k\lt l you have A_i+A_j = A_k + A_l.
After that things work out fairly directly; it might help if you wrote things out on paper.

  • Choose the four elements (1, 2, 4, 5)A_1 + A_2 = A_4 + A_5
  • Choose (1, 3, 4, 5)A_1 + A_3 = A_4 + A_5
  • Choose (2, 3, 4, 5)A_2 + A_3 = A_4 + A_5.

The RHS of every equation is A_4+A_5, so all the LHS-es must also be equal.
That’s where my statement “A_1 + A_2 = A_1 + A_3 = A_2 + A_3, all being equal to A_4+A_5” comes from.

A_1 + A_2 = A_2 + A_3, cancel out A_2 from both sides to get A_1 = A_3.
Do the same thing for the other pairs of equations to see that all three of them are equal.

2 Likes

Thanks for replying @iceknight1093 . The logic makes sense now :raised_hands: