Editorial for An Animal Contest 6 P4 - Buffet

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

Observation 1

Since we want to delay \min(a_i) from reaching 0 for as long as possible, it is always optimal for the waiter to keep choosing the smallest a_i. Thus, the problem is greedy.

Observation 2

We can reframe this problem into the following:

Given an array a of length N, you can increment any element in the array by S. Doing so incurs a cost of 1. How times can you perform this action such that the total cost incurred is less than \min(a_i)?

Subtask 1

When we simulate the process of incrementing the minimum value, some patterns begin to emerge.

Let x be the smallest a_i in the initial array. We first increment values equal to x, then followed by x+1, x+2 and so on. At some point, we will have a minimum a_i greater than or equal to x+S, in which case we will start incrementing values that have already been incremented before. Essentially, we first increment values in the range [x, x+S-1], then those in the range [x+S, x+2S-1], [x+2S, x+3S-1], [x+nS, x+(n+1)S-1] and so on.

How do we figure out when the buffet ends?
Let c be the total cost incurred so far. Based on observation 2, we know the buffet ends when we have \min(a_i)-c \le 0. For each range that we will increment, we can iterate through each element to check whether or not this condition is met. To improve our time complexity, we can group ranges that have the same number of elements and process them together.

Time Complexity: \mathcal{O}(N^2)
Subtask 2

Notice that if T rounds can be served, then T-1 rounds can also be served. Therefore, we can binary search for the final answer. For each guess, we simply need to check if incrementing the last complete range works or not.

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


There are no comments at the moment.