avelino_2013's blog

2013-2014 ACM-ICPC, NEERC, Moscow Subregional Contest Problem K
By avelino_2013, 11 years ago, In English

Hi everyone,

i was trying to do Moscow Subregional yesterday (at Codeforces Gym) and got stuck at problem K (The Top K Elements). After some thinking, all i could get is an O(n) approach, n<=10^8, which "apparently", or maybe certainly, leads to TLE. Could someone give me a hint on this problem?

Thanks.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hint: radix sort

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, this problem should be solved in O(n). Operations in the solution are very simple, so quite many of them can fit into two seconds.

→ Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

nth_element

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank You very much! My own version of nth_element was not as good as algorithm's. Just calling nth_element saved a lot of time.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is heap too slow? nlogk?

→ Reply