Jomax100's blog

C++ Declaring vector inside loop = TLE?
By Jomax100, history, 6 months ago, In English

Why does declaring vector inside of the loop result in TLE. Eg

Outside

vector<int> visited(n);
for(){
  visited.assign(n, 0);
  // other code;
}

Inside

for(){
  vector<int> visited(n);
  // other code;
}

In the problem below, the "outside" method is AC with 765ms, but the "inside" method is TLE at 3000ms.

Why? I can understand there must be some extra cost to re-allocate and de-allocate memory for the vector, but is the constant factor really that high? Time Complexity is the same (size of the vector), so I was quite surprised. Would be great if anyone can share more insights. Thanks!

Context: I was working Codeforces Round 938 (Div. 3), problem G: GCD on a grid.

Eg example accepted solution: https://mirror.codeforces.com/contest/1955/submission/260714562 vs TLE solution with declaration inside loop: 260714503 (recommend using CF compare)

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

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Jomax100 (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
  Vote: I like it -35 Vote: I do not like it

Firstly it is TLE and MLE. TLE — because computer needs some time to create dynamic array.

MLE — because you create, n times, dynamic array.

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

I learnt about this while solving the same problem, redeclaring the 2-D vectors again and again N times leads to TLE first due to extra time being taken for memory allocation. When values are assigned instead of creating a new 2-D vector everytime then it's way faster.

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +56 Vote: I do not like it

In your solution, it is not just a vector, but a vector of vectors. And the test where it fails seems to have m=1, in other words you have a vector of a lot of vectors of size 1. So my theory is: vector itself has some overhead to store its size, capacity etc, so creating a vector of size 1 uses overhead+1 operations, but assigning a vector of size 1 to another vector of size 1 takes just 1 operation. So with the vector outside the lambda you have n operations, and with vector inside the lambda you have n*(overhead+1) operations.

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

    You are 100% right! I changed the 2D vector to 1D, vector, and despite the defining the vector inside the loop, it was AC. 260881136

    I learned a valuable lesson about overhead and debugging. Thanks!

    → Reply