Editorial for BSSPC '21 J4 - James's Magical Soups


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

Subtask 1

For the first subtask, we make the greedy observation that for each minute, if there are multiple possible soups that we can choose to drink, it is always optimal to drink the one that expires the soonest (i.e. has the minimum F_i). Knowing this, we can naively loop through the soups every minute, always choosing to drink the soup with the minimum F_i out of the soups that are available to drink. It is helpful to note that the i^\text{th} soup is only drinkable when it is between \max(0, T_i - X) and F_i minutes old, inclusive.

Time Complexity: \mathcal O(N \max(F_i))

Subtask 2

For the second subtask, we can speed up our algorithm using a priority queue. First, we sort the soups in order of ascending T_i. Each minute, we can add any newly cool-enough-to-drink soups to the priority queue, then repeatedly pop the soup with the minimum F_i from the queue until either the queue is empty, or we find an unexpired soup to drink.

Time Complexity: \mathcal O(N \log N + \max(F_i))


Comments

There are no comments at the moment.