Editorial for DMOPC '17 Contest 3 P1 - An Early Christmas Present

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: Kirito

For $10\%$ ~10\%~ of points, it suffices to generate all $\mathcal O(N)$ ~\mathcal O(N)~ subsets of size $N-1$ ~N-1~, and calculate their average in $\mathcal O(N)$ ~\mathcal O(N)~ time.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For the remaining $90\%$ ~90\%~ of points, we can either compute an average in $\mathcal O(1)$ ~\mathcal O(1)~ time by subtracting the number we are considering from the total sum of all elements. Alternatively, we can make the observation that the number we wish to remove is the minimum. The proof is left to the reader as an exercise¹.

¹Who knows? Maybe your teacher will give you bonus points if you can present a fully rigorous proof.

Comments

There are no comments at the moment.