Editorial for MWC '15 #1 P3: Dolls


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.

To solve this problem, the number of occurrences of each doll needs to be stored prior to checking for the least and most frequent dolls. An integer array can be used to store the frequency of each doll. The index of each array will represent the doll price, and the integer in each index will represent the frequency of that particular doll. After the frequencies are stored, the frequencies in the array need to be checked in one cycle through the array. One variable records and updates the index (doll price) with the greatest frequency (in the case of ties for frequencies, the higher price doll is selected), and another records and updates the index (doll price) with the lowest frequency (in the case of ties for frequencies, the lower price doll is selected). Then, the absolute value of the difference of the highest and lowest frequencies is computed.

Time complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.