## 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 , 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 .

#### Solution — C++

#include <stdio.h>
#include <bitset>

int a,b,c,d;
std::bitset<100005> taken;

int main()
{
taken.flip();
scanf("%d%d",&a,&b);
for (int i=0; i<b; i++) {
scanf("%d",&c);
d=taken._Find_next(a-c);
if (d>a) {
printf("%d\n",i);
return 0;
}
taken[d]=0;
}
printf("%d\n",b);
}


• commented on Dec. 11, 2020, 12:52 a.m.

to confirm, even though the sample solution passes, it is demonstrating a naive (O(GP)) solution right? can't seem to find official documentation on this "._Find_next()" function, but from what ive seen on miscellaneous websites, it runs in O(n) (or something like O(n/32)) right?

was confused because i inferred that an O(Plog(G)) solution was needed to pass on dmoj

• commented on Dec. 10, 2020, 5:48 p.m. edited

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

• commented on Dec. 10, 2020, 6:48 p.m. edited

O(P(2logG)) = O(PlogG) since we disregard the constant factor