_asmah98's blog

Doubt in Priority Queue of strings complexity (TLE in recent div2 problem C)
By _asmah98, history, 5 years ago, In English

I know it is an overkill to use Priority Queue in recent Div 2 problem C but why does using it gives TLE on test case 32 in problem C ? isn't it O(nlogn), which should pass ?

Link to Submission

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

»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

It is possible to use Priority Queue without getting TLE. check My submission

But our implementations are different and no of Queue operations are higher in your solution. Maybe optimizing could get you off TLE. I have trouble understanding your code so i don't have any suggestions. Good luck tho :)

Edit: fixed the link No i can't :\ link : https://codeforces.net/contest/1348/submission/78739940

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

Yes. The Priority Queue is O(nlogn) but string comparison is very costly O(n) so the overall time complexity is O(n^2logn)

→ Reply