Editorial for Wesley's Anger Contest 2 Problem 2 - Costume Shopping


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.

Authors: Zeyu

To use a minimum amount of money to buy all the costumes, taking a greedy approach and buying the cheapest costume available for the day until we have M costumes will give us the correct answer.

To do this efficiently we can represent the entire N days as Q intervals of time, each spanning over some days until the next price change. By processing these Q intervals of time using the price from least to greatest, we can efficiently find the best days to buy costumes.

Special care must be given to adjacent intervals which intersect on their endpoints. Using a set or map will suffice for taking care of this case.

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


Comments

There are no comments at the moment.