I have an alternate thinking way, for the less math savvy ones even if this is a simple mathematical expansion. This approach can be generalized for other problems of finding maximas or minimas, so this problem could be used as an introduction to this format of thinking (it can save you a lot of time, especially if you are bad at rewriting expressions, and itās actually quite intuitive ).
First observation we can make is that for unordered pair (a, b), there are two possible outcomes:
-
(a \cdot b) + a - b, and
- (a \cdot b) + b - a
Itās obvious that for case a > b we should opt for the first equation, otherwise move to the second one. This way we can narrow down the list of possible candidates for each a, simply by sorting the array and considering only the lower elements as b.
Let the final array be [b_1, b_2, ..., b_n], in increasing order. Let us consider what happens for b and b', such that b' > b. We can express b' as b' = b + x. Again, we have two equations:
-
(a \cdot b) + a - b, and
- (a \cdot (b + x)) + a - (b + x) = (a \cdot b) + a - b + (x \cdot (a - 1))
A thing to notice is that when we subtract the first from the second equation we are left with:
(a \cdot b) + a - b + (x \cdot (a - 1)) - ((a \cdot b) + a - b) = x \cdot (a - 1)
Since x \geq 0, the final value is dependent only on a - 1, so we have two cases:
-
a > 0 \implies maximize x, since the array is sorted b is the first value before a
-
a \leq 0 \implies minimize x, since the array is sorted b is the first value in the array
So we can always uniquely determine the final index and weāve proven it is optimal.
This idea can be useful in much more advanced problems which have to do with minimality/maximality, one of which is CodeForces 1428E (not an easy problem per se, but the key to the solution is adapting the provided idea), so if any of you are curious hereās the link - Problem - 1428E - Codeforces.