m_nigam01's blog

By m_nigam01, history, 21 month(s) ago, In English

Hello, Codeforces!

I am solving this problem https://codeforces.com/contest/1665/problem/B

But I'm getting TLE on test case 13. I don't think there should be any TLE. Please look at my code and guide me what's wrong with my thought process. https://pastebin.com/EmhQpghv

I also optimized my code to get rid of inner while loop https://pastebin.com/5800fc8C But still get TLE on testcase 13.

Thanks for any help or suggestion!

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

endl is slow when you print lot of lines, use "\n" instead.

Here is an accepted submission.161839419

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks a lot for the help But I copied you code and getting TLE still https://codeforces.com/contest/1665/submission/161854064

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Submit in C++20 (64) language, not C++17

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know why this behavior but it got accepted thanks

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The problem is that you're using an unordered_map. The expected access time is in O(1) but in the worst case, when a lot of hash collisons occur it is O(n). This leads to your solution having a time complexity of O(n^2) which ist too slow. It seems to work with C++20 because it uses a different hash function and there is no designed testcase for this hash function. Your solution should be accepted if you use map instead of unordered_map.