NOTSUM - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting (optional)

PROBLEM:

You’re given an array A of length N.
Find any triplet of distinct indices (i, j, k) such that A_i + A_j \ne A_k, or say that no such triplet exists.

EXPLANATION:

We want A_i + A_j \ne A_k.
Observe that if we are able to make A_i \gt A_k, then no matter what the value of A_j is, we’ll have A_i + A_j \gt A_k because all the array elements are non-negative; and hence A_i + A_j \ne A_k will certainly hold.

With this in mind, a natural choice is to choose A_i to be the largest element of the array, and A_k to be the smallest element.

There are now two possibilities for our two chosen indices:

  1. A_i \gt A_k.
    Here, as noted earlier any choice of A_j will work, so just choose any index other than i and k.
  2. A_i = A_k
    This means the minimum and maximum of the array are equal; in which case all elements of the array are equal.
    In this case we can choose any j and the result will be the same either way.

In the second case, since we have A_i = A_j = A_k no matter the choice of j, we’ll almost always have A_i + A_j \gt A_k as well, since the left side will equal twice the right side.

The only exception is when A_i = A_j = A_k = 0, in which case both sides evaluate to 0.
Note that this is only possible when every element of the array equals 0, so this is the only -1 case - in every other case, the above solution of “pick i and k as the indices of the maximum/minimum respectively, then pick j arbitrarily” will always give a valid triplet.

Many other solutions are possible too - for example you can pick the largest two elements of the array as A_i and A_j and then A_k can be anything - for example the third largest element of the array.
The largest/smallest elements of the array can be found using an \mathcal{O}(N) loop, or by first pairing each element with its index and then sorting the array.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log 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(-1)
        continue
    
    b = [(a[i], i+1) for i in range(n)]
    b.sort()
    print(b[n-1][1], b[n-2][1], b[n-3][1]) # indices of largest three elements
1 Like