← All solutions

Problem authors: Jakub Onufry Wojtaszczyk and Federico Glaudo
Solved by 96 teams.
First solved after 33 minutes.
Shortest team solution: 669 bytes.
Shortest judge solution: 246 bytes.

This problem, which has absolutely no real-world inspirations, can be solved with a greedy approach with a short implementation.

One method to solve this problem is to first ignore the restriction that you cannot sleep while rested. This allows you to sleep during some intervals [e_i, b_i+1], where e₀ = 0. After sleeping during one such interval, we can be awake until e_i + 2(b_i+1 − e_i), so we greedily sleep during these intervals if they allow us to stay up later than we currently can.

After having a list of sleeping intervals from the above process, we need to modify them such that the beginning of one sleep interval is not in the k minutes after the end of the previous one. To do so, say two consecutive sleep intervals are [s_i, t_i] and [s_i+1, t_i+1]. Then we need s_i+1 ≥ t_i + (t_i − s_i) = 2t_i − s_i ⇔ (s_i+1 + s_i)/2 ≥ t_i. Thus we set t_i to the mean of s_i and s_i+1 if needed.