Editorial for WC '16 Contest 4 J2 - You're Dead!
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 , 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 time, or in 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 time.
Comments