CandidFlakes's blog

Why am I getting TLE ?
By CandidFlakes, history, 11 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

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

Auto comment: topic has been updated by CandidFlakes (previous revision, new revision, compare).

→ Reply
»
11 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
»
11 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

adding to what people already said about unordered_map, you are also using endl, which automatically flushes the stream. this operation is slow, so you should almost always prefer using a simple newline (\n).

→ Reply