Editorial for TLE '16 Contest 1 P2 - Heavy-Light Decomposition


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

This is another relatively straightforward problem.

Note that in order for Flaco to take the minimal number of boxes, he should choose the average that is the least.

The most challenging average to compute is the mode; since all numbers with the highest frequency must be stored. We can first count the frequency of each number. Next, declare a vector and iterate through all distinct numbers. If the frequency of the number is higher than the currently recorded frequency, clear the vector and insert the number. Otherwise, if the frequency of the number is equal, push the number into the vector.

Mean and median are easy to compute, but keep in mind that a sort should be used to calculate the median.

After finding the smallest average, count all boxes that have a weight less than or equal to this average using iteration or a binary search (if boxes are sorted).

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.