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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 , 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 .
Comments
Is there anyone passed this question by using python3 set? I failed and there is a lot TLE.
try pypy
Why do we need to use set?
This comment is hidden due to too much negative feedback. Show it anyway.
since we disregard the constant factor