Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

CandidFlakes's blog

Why am I getting TLE ?
By CandidFlakes, history, 16 months ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
16 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

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

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

→ Reply