NITIN_K_SHUKLA's blog

Is allocating too much of memory every time causes TLE in the code?
By NITIN_K_SHUKLA, history, 3 years ago, In English

Hello Coders I want to ask one thing that In this question 1592A - Gamer Hemose when I am solving it with using vectors then I got AC you can see my submission 134683722 and when I am solving this with same concepts except here I am using array then I got TLE on test 7 134684129.Why it is happening?

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

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In the submission that gets TLE, you declare a big array every time (for each test). If you keep the array v in the global scope instead of inside function solve you should get AC

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    Yes I have used this thing already and got ac but I am not able to understand why I got TLE if I declare big array every time. I mean what is wrong with this.

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

      let's say the time complexity of declaring an array with a size of N is around $$$O(N)$$$

      If you declare it $$$N$$$ times it becomes $$$O(N^2)$$$ which means too slow. I think this is the main reason why you're getting TLE.

      Also, there is this thing called cache. I don't actually read it but I do know that if it becomes too big it slows down overall execution time.

      I've made a simple code that declares big massive. This is the source code: 134732816. You can see that it works over 1sec in the result.

      It might not be correct. But If you have the correct answer, can you leave it under replying. thank you :)

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

        yes, actually declaring a 200000-element array 10000 times already touches the 1-second limit. Moral: don't overdo memset.

        → Reply