VandanRogheliya's blog

My code's logic and editorial's logic is the same, then too time limit exceeded!
By VandanRogheliya, history, 4 years ago, In English

Sorry for this noob question, I am new to competitive coding. I want to know what in my code is causing "time limit exceeded". Link to my code

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Let me say, you are asking OS for two arrays of length $$$2000001$$$ in each test case, and you set the arrays' elements equal to 0, which is $$$O(n)$$$, in other words you are doing $$$2000001$$$ iterations for each test case, its just too much. You dont have to clear all the array, you just need to clear first $$$n+1$$$ elements.

Iv'e cleared that and submitted your solution, it works very fast.

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

    I think his code got TLE due to his typo. I mean he intended to declare temp1 and temp2 with size 200001, but somehow he typed 2000001 accidentally and got TLE. I edited his solution 80785027

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

      See the time, the solution runs in about 900ms(it luckily passes), but mine works in about 80ms, indeed you are right but the main problem that caused TLE was that he was doing $$$O(MaxN)$$$ iterations for each test case.

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

      No, it was not a typo. I wanted that big array XD. Thank you for looking into my code!

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

    Oh, I got it! That is why most of the answers declare arrays globally of that size. Thanks for the fast response!

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The constraint in the statement is 2e5, yours is 2e6! Edit temp1 and temp2 size to 2e5 then your problem could be solved!

→ Reply