CCC '15 S3 - Gates

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Python 2 5.0s
Python 3 5.0s
Memory limit: 256M

Author:
Problem type
Canadian Computing Competition: 2015 Stage 1, Senior #3

For your birthday, you were given an airport.

The airport has G gates, numbered from 1 to G. P planes arrive at the airport, one after another. You are to assign the i^{th} plane to permanently dock at any gate 1, \dots, g_i (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 (1 \le G \le 10^5), the number of gates at the airport.

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

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

Note that for at least 20\% of the marks for this question, P \le 2\,000 and G \le 2\,000.

Output Specification

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

Sample Input 1

4
3
4
1
1

Output for Sample Input 1

2

Explanation of Output for Sample Input 1

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

Sample Input 2

4
6
2
2
3
3
4
4

Output for Sample Input 2

3

Explanation of Output for Sample Input 2

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


Comments


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

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


  • 3
    Ken_Shi  commented on Jan. 11, 2017, 9:21 p.m.

    Even the O(n ^ 2) Algorithm worked as long as you code it in C


    • -11
      Kirito  commented on Jan. 13, 2017, 7:08 p.m.

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


      • 5
        Ken_Shi  commented on Jan. 16, 2017, 11:17 a.m.

        I still passed lol.


  • -2
    Shehryar  commented on Jan. 4, 2017, 7:52 p.m.

    Implementing a TreeSet will hold back your worries about TLE.


  • 0
    Kevin_Pan  commented on Aug. 9, 2016, 12:04 p.m.

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


    • -1
      bobhob314  commented on Aug. 11, 2016, 12:34 p.m. edited

      nvm i'm tired, pls delete this comment mods


  • 1
    Day  commented on Aug. 6, 2016, 9:15 a.m.

    I think Java is missing in the allowed languages.


    • 1
      Xyene  commented on Aug. 6, 2016, 3:05 p.m.

      Thanks for letting us know, it's been added now.


  • -2
    Tan  commented on May 17, 2016, 10:26 p.m.

    Why is there no judge for this problem?


  • 1
    andrew498  commented on Aug. 3, 2015, 4: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?


    • 3
      kobortor  commented on Aug. 3, 2015, 11:19 a.m.

      Your algorithm is wrong, one possible approach is to use binary search and a set to reduce to run time complexity to O(P log G)

      Not sure what the set equivalent is in java though.


  • 19
    bobhob314  commented on May 18, 2015, 9:45 a.m.

    TIL that 10^5 ≠ 10000.


  • 15
    quantum  commented on Feb. 22, 2015, 1: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\% of the CEMC cases, P \le 2\,000 and G \le 2\,000. Those cases are worth 20\% of the total points.