Editorial for Mock CCC '18 Contest 2 J3/S1 - An Array Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: xiaowuc1

The answer is:

$\displaystyle \min\left(\sum_i a_i - \max_i a_i, \left\lfloor \frac{\sum_i a_i}{2} \right\rfloor\right)$

The left expression is an upper bound on the answer because if we consider the $n-1$ ~n-1~ smallest elements, each operation has to decrease at least one of those entries.

The right expression is an upper bound on the answer since the sum of the list decreases by $2$ ~2~ per operation and cannot be negative.

If the left expression bounds the answer, then the optimal arrangement is to always decrease the maximal element once and force the other elements to zero.

If the right expression bounds the answer, we can simultaneously decrease the smallest and largest element and repeat this until the list contains at most one $1$ ~1~.

Comments

4

Evang commented on Nov. 1, 2020, 2:57 a.m. ← edited →

$min(sum(a) - max(a), \left \lfloor{sum(a)/2}\right \rfloor)$ is the answer, if anyone finds the notation a little difficult to read (note: $sum(a)$ ~sum(a)~ is the sum of all elements and $max(a)$ ~max(a)~ is the max value of $a$ ~a~).