## Editorial for Another Contest 1 Problem 3 - Poutine

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

We start by considering the case where . In this situation, it is clearly optimal to order the poutine with the highest value.

Consider a situation where . Is it ever optimal to ignore the poutine with the highest value and choose some other types? We claim the answer is no, and we use a proof by contradiction here. Note that ordering a poutine more than once does not increase the utility that it provides. Consider some optimal selection order of poutine that does not include the poutine with the highest value at all. Note that no order of poutine can provide utility strictly larger than as a result, but this means we can arbitrarily substitute some chosen poutine with the one that has the highest value. This does not decrease the utility gained (and in fact may increase it). This implies that we should always select the poutine with the highest value at every step.

This directly gives an algorithm, of the following form:

```
Repeat the following T times
Find the poutine that gives the maximum utility now, and order it
```

However, can be as large as , so this algorithm will be too slow. Therefore, we have to do better than simulate this process one step at a time.

If we look at the structure more carefully here, we note that the utility values that we gain at each time step are nonincreasing. Because of this, we can perform a binary search on the utility that Thomas will gain on the th iteration of this algorithm. Let this value be . Thomas will look at each poutine in turn and order it until the utility gained from it no larger than . Repeat this for every poutine. After this point in time, some poutines will give exactly utility. If this can account for exactly orders, then is the correct answer. Otherwise, either it accounts for too many orders, in which case we increase , or it accounts for too few orders, in which case we decrease .

## Comments

in my contest 4th submit is wrong but with '\n' i get accepted

what a f situation

In the contest page, it was described that all problems are graded with an

`identical`

checker, and that you needed to have all lines terminate with a`\n`

character.sorry my mistake

I still don't get accepted with \n. Stuck on the 4th Case with Java. My algorithm seems to be working fine tho

this editorial is not enough!!! additionally print answer with '\n' must need

This was specified on the contest page: https://dmoj.ca/contest/acc1

wow I miss it. But, in Sample Output there is none exsist '\n'

This comment is hidden due to too much negative feedback. Click here to view it.

really?

at windows10 Microsoft edge copy and paste to notepad

any new line I can't found it where is it ? XD