Please read the new rule regarding the restriction on the use of AI tools. ×

esho_moja_kori's blog

Why TLE in 144th testcase? Can't figure out.
By esho_moja_kori, history, 4 months ago, In English

Here is the problem: https://codeforces.me/contest/1980/problem/C and here is my submission: https://codeforces.me/contest/1980/submission/264001404 What did I do wrong?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
The time complexity of your code is O(t*(nlogn + m*logm*logm)) (since every map access cost around O(logn) complexity).
Particularly this part of your code causes the logarithmic factor to be quadratic.
So, when m tends to 2*10^5. your code performs around 5.6*10^6 operations per second and since, the time limit is 2s, your code just barely TLEs in this case.
→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't that highlighted part of code 3*log(m), why are we multiplying the logarithmic operations?

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

      You are right, then the TLE might be because of constant factor being too high.

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

    5.6*10^7, actually. 5.6*10^6 should almost never TLE, but anything times 10^7 can TLE easily with constant factor.

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

You are using the map's read operation thrice in a loop which goes till M. Then you are using 2 map read operations in a loop which goes till N. Then you have another loop with NLogN complexity. So O(3NLogN + 3MLogM), for the N=M=2*10^5. You are doing close to 2.2 *10^7 operations, which might cause TLE.

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

    Not using Fast IO can also be a factor for TLE.

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

I submitted your code but with only two different lines , defining endl to be ”\n" , and using the fastIO macro , and it passed Here's the submission 264177806

In general avoid using endl because it does flushing to the output stream which can cause TLE

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

This works in two simple ways.

  1. Using FastIO. 2.Removing unused maps.

Thank you guys for responding.

→ Reply