Блог пользователя Dark_knight174

Автор Dark_knight174, история, 4 недели назад, По-английски

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://codeforces.me/contest/1654/problem/C

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

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This works: https://codeforces.me/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.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I dont think it should give TLE?

    • »
      »
      »
      4 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 недели назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.