Editorial for CCC '15 S3 - Gates

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.

Author: FatalEagle

A simple greedy algorithm goes like this:

For each plane, assign it to the gate with the largest number that isn't occupied.

It's not hard to see why this is correct — indeed, intuitively, we're using the "worst" gate we can for each plane (since a gate with a lower number can serve at least every plane a gate with a higher number can).

Implementing this naïvely will result in a complexity of O(GP), which is enough for the weak data used on the actual CCC. To speed this up, we can use a balanced binary search tree to store free gates. In C++, this is the set data structure, with a final time complexity of O(Plog⁡G).

Comments


  • 0
    Stonks  commented 47 days ago

    Can't you use an array to store the largest possible gate? It can start with arr[i] = i and the time complexity is just O(P)


  • 0
    Frrrank  commented on Jan. 30, 2024, 3:33 p.m.

    Is there anyone passed this question by using python3 set? I failed and there is a lot TLE.


    • 0
      Viv_CCGS  commented on Oct. 4, 2024, 6:28 a.m.

      Yeah, I passed, but not with set. I used segtree. I recommend learning segment tree for this problem if you want to do it in python.


    • 0
      htoshiro  commented on Jan. 30, 2024, 6:52 p.m.

      try pypy


  • 5
    cz52013141834  commented on July 13, 2022, 7:37 p.m.

    Why do we need to use set?


  • -17
    bigboy2  commented on Dec. 10, 2020, 10:48 p.m. ← edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 20
      a_sad_javamain  commented on Dec. 10, 2020, 11:48 p.m. ← edit 2

      O(P(2log⁡G))=O(Plog⁡G) since we disregard the constant factor