Блог пользователя NITIN_K_SHUKLA

Is allocating too much of memory every time causes TLE in the code?
Автор NITIN_K_SHUKLA, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -23 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

      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 :)

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить