Shreyansh_1347's blog

Why am I getting a TLE ?
By Shreyansh_1347, history, 4 months ago, In English

I exactly implemented the tutorial for the problem G. Hits Different. The solution they gave looks like they have the same time complexity as mine. But still, I get a TLE on test case 2. My Submission

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

»
4 months ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Pass by (const) reference unless you have a reason not to do so.

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

    +1

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

    Did that but still getting a TLE. My Submission

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

      "The solution they gave looks like they have the same time complexity as mine."

      I haven't read the problem. However, there is another nested loop in sum(). I can't find why they have the same complexity.

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

They did a precomputation of the main algorithm that you are doing every time for every test case. The time complexity for your solution is ~ T * (1500*(1500+1)/2) (considering the nested for loops in solve() and the loops in sum() function). So in the worst case, it goes upto ~1.125 * 1e9 number of iterations. What the solution does is it precomputes the main algorithm in ~1.125*1e6 and then for each test case, it is performing an O(1) operation. So in the worst case, it won't exceed 2.5*1e7 which is roughly 2.5sec (if I take 1e7 iterations in one sec).

→ Reply