## Editorial for An Animal Contest 6 P4 - Buffet

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

## Observation 1

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

## Observation 2

We can reframe this problem into the following:

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

## Subtask 1

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

Let be the smallest in the initial array. We first increment values equal to , then followed by , and so on. At some point, we will have a minimum greater than or equal to , in which case we will start incrementing values that have already been incremented before. Essentially, we first increment values in the range , then those in the range , , and so on.

How do we figure out when the buffet ends?

Let be the total cost incurred so far. Based on observation 2, we know the buffet ends when we have . 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:**

## Subtask 2

Notice that if rounds can be served, then 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:**

## Comments