PROBLEM LINK:
Author: Sergey Kulik
Tester: Vlad Mosko
Editorialist: Pushkar Mishra
DIFFICULTY:
Cakewalk
PREREQUISITES:
Sorting
PROBLEM:
Given an array A of length N, remove the smallest and largest K elements from it and then calculate the average.
EXPLANATION:
Subtask 1
For this subtask, K = 0. This means that we don’t have to remove any element from the given input array A. The only thing that remains now is to calculate the average of this array. For that, we simply take the cumulative sum of all the elements and divide it by the length of the array. Care needs to be taken about the data types used. We want to do all the operations in the double type so that the final answer is precise to the required decimal places.
This algorithm requires a simple scan of the array. Therefore, the complexity is \mathcal{O}(N).
Subtask 2
In this subtask, K > 0. This means that we have two exclude certain number of smallest and certain greatest numbers in the input array. What is the fastest method to determine the smallest and the greatest K numbers? Sorting. We can sort the array in ascending order. Then the first K elements are the smallest K elements and the last K elements are the greatest K elements. After sorting, we simply sum over the elements excluding the first and the last K elements and divide the result by N-2K. Again, care is to be taken regarding data types being double.
We can’t use an \mathcal{O}(N^2) sorting method because that wouldn’t run in time (note that there are 100 test cases per file). So, we have to use an \mathcal{O}(N\log N) sorting like the quicksort, mergesort, or the in-built sorts in most of the programming languages. Since sorting is the heaviest operation in the algorithm, the complexity is \mathcal{O}(N\log N).
Editorialist’s program follows the editorial. Please see for implementation details.
OPTIMAL COMPLEXITY:
\mathcal{O}(N\log N) per test case.