Editorial for RGPC '18 P3 - Chocolate Day


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

To efficiently calculate the number of chocolates in each cup, use a difference array to handle the range updates.

Next, use a sliding window/two pointer approach to find groups of cups, or subarrays, with a total sum under the given limit. Keep track of the endpoints of the current subarray. Increment the right endpoint if the subarray's sum is under the limit to check if adding the next cup still produces a valid answer. Increment the left endpoint if the sum is over the limit since there are no more valid subarrays starting from this cup.

When moving the left endpoint, update the answer if the length of the subarray before the right endpoint was moved (i.e. how many cups fit under the limit) is greater than the current maximum. Be sure to increment and decrement the sum counter accordingly.

Time complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.