Editorial for New Year's '18 P3 - World Domination Fun

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

For the first subtask, it is enough to keep track of the snowmen with the smallest height. If Bob can pick a subarray of length M with all of them in it, then the answer is that height plus one. Otherwise, the answer is that height.

Time Complexity: \mathcal O(N)

For the next subtask, sort the snowmen by their heights. Then calculate how much snow is necessary to bring all the shorter snowmen to the same height as the i^\text{th} shortest snowman. Determine the largest such i where the amount of snow (K) is enough. Then you can increase the heights of all these i snowmen by the amount of snow left divided by i (you need to take the floor of this).

Time Complexity: \mathcal O(N \log N)

For the final subtask, we binary search for the largest possible strength. Given a certain strength, we can determine the minimum amount of snow necessary to achieve this strength using the following idea:

Loop through the snowmen from left to right. If a snowman shorter than the strength is encountered, increase that snowman's height to the certain strength. At this point, there is a choice. There are many subarrays of length M which contain this snowman, so which one should be used? Note that based on this algorithm, the snowmen before the snowman you just reached should have height \ge the strength, so there is no need to increase their heights. So it is best to choose the subarray starting from the current snowman. We can update this subarray using only a difference array, since we are considering the snowmen in order.

Time Complexity: \mathcal O(N \log K)


There are no comments at the moment.