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

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

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


Comments


  • 1
    leehoss  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


    • 4
      Rimuru  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.


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

        sorry my mistake


        • -4
          VOiD  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


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

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


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

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


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

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


        • -5
          嗨我很迟钝  commented on Oct. 17, 2018, 10:23 a.m.

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


          • -2
            leehoss  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