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 $T=1$ ~T=1~. In this situation, it is clearly optimal to order the poutine with the highest $a_i$ ~a_i~ value.

Consider a situation where $T > 1$ ~T > 1~. Is it ever optimal to ignore the poutine with the highest $a_i$ ~a_i~ 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 $a_i$ ~a_i~ value at all. Note that no order of poutine can provide utility strictly larger than $a_i$ ~a_i~ as a result, but this means we can arbitrarily substitute some chosen poutine with the one that has the highest $a_i$ ~a_i~ 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 $a_i$ ~a_i~ value at every step.

This directly gives an $\Omega(T)$ ~\Omega(T)~ algorithm, of the following form:

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

However, $T$ ~T~ can be as large as $10^{18}$ ~10^{18}~, 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 $T$ ~T~th iteration of this algorithm. Let this value be $v$ ~v~. Thomas will look at each poutine in turn and order it until the utility gained from it is no larger than $v$ ~v~. Repeat this for every poutine. After this point in time, some poutines will give exactly $v$ ~v~ utility. If this can account for exactly $T$ ~T~ orders, then $v$ ~v~ is the correct answer. Otherwise, either it accounts for too many orders, in which case we increase $v$ ~v~, or it accounts for too few orders, in which case we decrease $v$ ~v~.

Comments

0

leehoss commented on Oct. 17, 2018, 1:01 a.m.

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

what a f situation

4

Rimuru commented on Oct. 17, 2018, 2:27 a.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.

1

leehoss commented on Oct. 17, 2018, 4:14 a.m.

sorry my mistake