Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

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

Автор CandidFlakes, история, 16 месяцев назад, По-английски

I am trying to solve this question.

I have made use of unordered map to store the frequency of each doll size and then I count the sets by subtracting the difference between the consecutive frequency, If we are considering element a then we look for the frequency of element a-1, if the frequency of element a-1 is less than frequency of element a, then we increase the count of set by frequency(a)-frequency(a-1). It seems to be working fine but I am getting TLE in test case 28. Here, is my submission.

Why am I getting TLE? Please suggest changes to remove this TLE error.

I will be thankful for any help!

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

»
16 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

This case is pretty typical
iirc it's because the time complexity of unordered_map can be blown up to $$$O(n^2)$$$.
you can see this post for more information

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

Change unordered_map to map

Don't forget Worst time complexity of Hash-map is O(N) not O(log(N))

i have submitted 219563923 you same code by changing unordered_map to map and it got accepted