## Editorial for Another Contest 1 Problem 3 - Poutine

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.

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 .

• commented on Oct. 16, 2018, 9:01 p.m.

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

what a f situation

• commented on Oct. 16, 2018, 10:27 p.m.

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.

• commented on Oct. 17, 2018, 12:14 a.m.

sorry my mistake

• commented on Oct. 19, 2018, 2:41 a.m. edited

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

• commented on Oct. 16, 2018, 8:57 p.m.

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

• commented on Oct. 16, 2018, 9:16 p.m.

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

• commented on Oct. 16, 2018, 9:19 p.m. edited

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

• commented on Oct. 17, 2018, 10:23 a.m.

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

• commented on Oct. 17, 2018, 10:54 a.m. edit 3

really?

at windows10 Microsoft edge copy and paste to notepad

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