Editorial for WC '16 Contest 4 J2 - You're Dead!


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.

Due to the constraint that the temperatures of challenges chosen on any given day may not differ by more than L^\circ, it makes sense to try to group challenges with similar temperatures together into the same days. As such, let's start by sorting the challenges' temperatures in non-decreasing order (which can be done in \mathcal O(N \log N) time, or in \mathcal O(N) time if we take advantage of the small range of possible temperatures).

Then, we can iterate over the challenges in non-decreasing order of temperature, grouping them together into as few days as possible. As we go, if the next challenge can be validly grouped into the same day as the previous challenge, then it's optimal to greedily do so – it can't help to save it for a later day. With this in mind, we can keep track of the number of days used so far, the number of challenges already allocated to the current day, and the temperature of the current day's first challenge (which dictates the maximum allowable temperature of the day's final challenge). This information can then be used to determine whether the next challenge can be added onto the current day, or if it must instead be the first challenge on the following day. This greedy process can be implemented in \mathcal O(N) time.


Comments

There are no comments at the moment.