Dark_knight174's blog

Why does it TLE?
By Dark_knight174, history, 2 months ago, In English

I submitted the same solution on two c++ compilers g++ 17 and g++ 20 . On g++ 20 my solution ran quite fast and got ac in 200ms . on the other hand on g++ 17 it got TLE with 2000ms runtime . I dont know whether the issue is with the time complexity of my solution or the compiler?

here is the link for the problem : https://mirror.codeforces.com/contest/1654/problem/C

here are my submissions: (AC) https://mirror.codeforces.com/contest/1654/submission/288743518

(TLE) https://mirror.codeforces.com/contest/1654/submission/288743107

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

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

This works: https://mirror.codeforces.com/contest/1654/submission/288782927

Replaced existence check from s1.count(n) to s1.find(n) because you were calling already s1.erase(s1.find(n)) inside if statement.

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

    I dont think it should give TLE?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If you think about it you don't need the actual count of elements equal to $$$n$$$ but instead you just need to remove the first one of the many elements equal to $$$n$$$.

      Read this blog on how $$$count$$$ performance in the case of $$$multiset$$$ might become $$$O(n^2)$$$ when you have a lot of elements equal to $$$n$$$.

      I'm not surprised in later implementations of the standard library they decided to improve $$$count$$$ performance on pathological edge-cases with many equal elements

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I didn't knew it. Thanks for sharing . I was in habit of using count and it never gave me TLE in case of sets but here it was multiset and I didn't noticed that.

        → Reply