Hints → https://atcoder.jp/contests/arc158/editorial/5987

The value in question is symmetric with respect to \(i, j, k\), so let us forget the order \(1≤i<j<k≤N\) and just choose distinct three numbers.

Additionally, the sequence \(x\) may contain the same value multiple times, but let us order those occurrences of the same value in some way to distinguish all of them.

[1] Narrow down the candidates

Let us begin with a simple case: if \(x_i\) and \(x_j\) are already chosen, what are the optimal \(x_k\)?

If we let \(a = x_i + x_j\) and \(b = x_ix_j\), the value is question can be written as:

\[\frac{x_i+x_j+x_k}{x_ix_jx_k} = \frac{a+x_k}{bx_k} = \frac{a}{b}\cdot \frac{1}{x_k} + \frac{1}{b}.\]

It can be seen that this value is maximized (or minimized) when \(1/x_k\) is maximum or minimum (depending on the signs of \(a\) and \(b\), the maximum value of the objective function may correspond to either the maximum or minimum value of \(1/x_k\), but anyway, it is enough to check the maximum and minimum values of \(1/x_k\)).

Even if we consider \(x_i\) and \(x_j\), which are already chosen, we only need to consider six values for \(x_k\): the ones with the three largest and three smallest values of \(1/x_k\).

[2] Solution

Let \(X\) be the multiset of elements \(x\) of the original sequence with the three largest and three smallest values of \(1/x_i\).

We have seen that we only need to check \(x_k \in X\) in search of an optimal solution. Similarly, it can be seen that we only need to check \(x_i, x_j\in X\).

Thus, we can solve the problem as follows.

• Sort the given sequence in ascending order of \(1/x_i\). Let \(X\) be the multiset of the first three and last three elements of the sorted sequence.
• Try all ways to choose three from \(X\) and print the minimum and maximum results.

When sorting by \(1/x_i\), you can actually compute the values of \(1/x_i\) or do the following: sort the negative numbers in descending order and the positive numbers in descending order, and then concatenate the results.

This method has the time complexity of \(O(N\log N)\). Since it is not necessary to sort the whole sequence, and it is only necessary to select the top and bottom three, we can solve the problem in \(O(N)\) time, too.

(Japanese version has some more information.)