Блог пользователя avelino_2013

2013-2014 ACM-ICPC, NEERC, Moscow Subregional Contest Problem K
Автор avelino_2013, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hint: radix sort

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

nth_element

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is heap too slow? nlogk?

→ Ответить