CCC '15 S3 - Gates - Olympiads Online Judge

CCC '15 S3 - Gates

Points: 10 (partial)

Time limit: 1.0s

Python 2 2.5s

Python 3 2.5s

Memory limit: 256M

Author:

SourSpinach

Problem type

Canadian Computing Competition: 2015 Stage 1, Senior #3

For your birthday, you were given an airport.

The airport has $G$ ~G~ gates, numbered from $1$ ~1~ to $G$ ~G~. $P$ ~P~ planes arrive at the airport, one after another. You are to assign the $i^{th}$ ~i^{th}~ plane to permanently dock at any gate $1, \dots, g_i$ ~1, \dots, g_i~ ( $1 \le g_i \le G$ ~1 \le g_i \le G~), at which no previous plane has docked. As soon as a plane cannot dock at any gate, the airport is shut down and no future planes are allowed to arrive.

In order to keep the person who gave you the airport happy, you would like to maximize the number of planes starting from the beginning that can all dock at different gates.

Input Specification

The first line of input contains $G$ ~G~ ( $1 \le G \le 10^5$ ~1 \le G \le 10^5~), the number of gates at the airport.

The second line of input contains $P$ ~P~ ( $1 \le P \le 10^5$ ~1 \le P \le 10^5~), the number of planes which will land.

The next $P$ ~P~ lines contain one integer $g_i$ ~g_i~, ( $1 \le g_i \le G$ ~1 \le g_i \le G~), such that the $i^{th}$ ~i^{th}~ plane must dock at some gate from $1$ ~1~ to $g_i$ ~g_i~, inclusive.

Note that for at least 3 marks for this question, $P \le 2\,000$ ~P \le 2\,000~ and $G \le 2\,000$ ~G \le 2\,000~.

Output Specification

Output the maximum number of planes that can land starting from the beginning.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

The first plane can go anywhere, but it is best to not put it into Gate $1$ ~1~. Notice that planes $2$ ~2~ and $3$ ~3~ both want to dock into Gate $1$ ~1~, so plane $3$ ~3~ is unable to dock.

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

The first two planes will dock in gates $1$ ~1~ and $2$ ~2~ (in any order). The third plane must dock at Gate $3$ ~3~. Thus, the fourth plane cannot dock anywhere, and the airport is closed, even though plane $5$ ~5~ would have been able to dock.

Comments

0

jerrycui07 commented on Nov. 15, 2023, 11:24 p.m.

Somehow my solution passed batch 1 fine, except for an IndexError on test case 4. Has anyone else encountered this issue?

0

b_nary commented on Nov. 16, 2023, 12:51 a.m. ← edited →

make sure to check if your planes gate list is empty (if it is then do not continue to pop)

50

TrevorYeung commented on Sept. 20, 2021, 3:34 a.m.

sick birthday present

1

zhenga1 commented on Feb. 10, 2021, 3:14 p.m.

hi can someone give me a hint to how to implement an equivalent of the std::bitset's _find_next() function in python?

1

Riolku commented on June 30, 2021, 7:01 p.m.

You should implement a solution with the correct complexity instead. Bitset is not the best way to approach this problem.

0

DynamicSquid commented on Dec. 27, 2020, 9:58 p.m.

For Batch #11 Case #3, I got a TLE; however, on the official CCC grader, my submitted code gets full marks since the time limit is 5 seconds. So are the problems here supposed to be mirror's of the one's found on other websites? Or could there be minor differences like time limit?

7

Narcariel commented on Dec. 27, 2020, 10:35 p.m. ← edit 2 →

In the second set of cases they augmented the test data to eliminate weaker solutions (That can still pass on the CCC). You have to find a more efficient solution to pass the second set of cases, try looking at the data structure set.

12

kujiyh commented on Dec. 23, 2020, 12:27 a.m.

What kind of person gets an airport as their birthday...

2
Nils_Emmenegger commented on Dec. 10, 2020, 9:31 p.m. ← edit 3 →
I think my solution is broken, but it still passes. Using this test case

5 5 1 2 3 5 5

my solution outputs 4, even though it should be 5. Did I misunderstand something, or has my solution miraculously passed despite being wrong?

Thanks in advance!

Edit: just solved the problem the right way, the solution I am referring to above can be found at https://dmoj.ca/submission/3196239

1

corgi commented on May 20, 2020, 4:31 p.m. ← edited →

Can anyone tell me why std::lower_bound TLEs, but set::lower_bound ACs? I thought they both ran in $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~

12

wleung_bvg commented on May 20, 2020, 9:23 p.m. ← edited →

set::lower_bound is a specialized lower_bound method for std::set that runs in $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ time. std::lower_bound only has this guarantee for random access iterators, which std::set does not have. For non-random access iterators such as with std::set, it takes $\mathcal{O}(N)$ ~\mathcal{O}(N)~ time on average (based on https://cplusplus.com/reference/algorithm/lower_bound/).

32

ScriptKitty commented on July 18, 2018, 7:34 p.m.

La-da-da-da-dah You know I'm mobbin' with the T.L.E.

3

bariumlanthanum commented on June 29, 2021, 2:05 p.m.

make this a real remix of the song

16

Ken_Shi commented on Jan. 12, 2017, 2:21 a.m. ← edited →

Even the $\mathcal{O}(n^2)$ ~\mathcal{O}(n^2)~ algorithm worked as long as you code it in C

-39

Kirito commented on Jan. 14, 2017, 12:08 a.m.

Not anymore!

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

44

Ken_Shi commented on Jan. 16, 2017, 4:17 p.m.

I still passed lol.

1

Shehryar commented on Jan. 5, 2017, 12:52 a.m.

Implementing a TreeSet will hold back your worries about TLE.

0

Kevin_Pan commented on Aug. 9, 2016, 4:04 p.m.

How come my 15/30 submission did not get TLE.

3

andrew498 commented on Aug. 3, 2015, 8:44 a.m.

Is it advised not to use ArrayList as it is slower than a regular array to optimize the speed of the program? Is the difference between an array and an ArrayList not large enough to slow down the program so drastically that the time limit would not be exceeded? If not, then it must be the algorithm that is at fault then, correct? And if so, any tips on how to optimize my algorithm?

4

kobortor commented on Aug. 3, 2015, 3:19 p.m. ← edit 2 →

Your algorithm is wrong, one possible approach is to use binary search and a set to reduce the time complexity to $\mathcal{O}(P \log G)$ ~\mathcal{O}(P \log G)~.

Not sure what the set equivalent is in Java though.

41

bobhob314 commented on May 18, 2015, 1:45 p.m. ← edited →

TIL that $10^5 \ne 10000$ ~10^5 \ne 10000~.

19

quantum commented on Feb. 22, 2015, 6:44 p.m. ← edited →

The original CEMC test data is now a 50% subtask (5 points). New cases, worth the other 50%, are added to award to the truly correct solutions.

All submissions have been rejudged.

Note: For $40\%$ ~40\%~ of the CEMC cases, $P \le 2\,000$ ~P \le 2\,000~ and $G \le 2\,000$ ~G \le 2\,000~. Those cases are worth $20\%$ ~20\%~ of the total points.