JigolKa's blog

TLE on Hello 2025 B
By JigolKa, history, 39 hours ago, In English

Hello,

I don't understand why my solution got a TLE for problem B. Here is the solution I came up with during the contest: 299645061. I'm quite sure the complexity is O(nlogn) but maybe I'm wrong. Here is another solution that doesn't use del: 299814673 even though if I remember correctly the complexity of del is O(1).

Does anyone have similar results?

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

»
39 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

You got hacked due to hash collisions blowing up your map/dictionary (which Counter is basically). See this blog.

Best way I found of fixing this was to just use str(yourInt) as the keys.

→ Reply
  • »
    »
    27 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is also an anti hash test for strings

    → Reply
  • »
    »
    24 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes this worked! Thanks! Do you know why it works?

    → Reply
»
39 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

quit python learn c++ = no more headache

→ Reply
»
24 hours ago, # |
  Vote: I like it -8 Vote: I do not like it

Hash collision is the main reason for getting TLE . Your code works O(1) per number which results O(n) for whole array most of the time.But due to hash collision it would be increased to O(n^2) which is inefficient for large inputs.

Hope this helps

→ Reply