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://codeforces.me/contest/1955/submission/260714562 vs TLE solution with declaration inside loop: 260714503 (recommend using CF compare)

According to https://cplusplus.com/reference/string/string/substr/ Complexity = Unspecified, but generally linear in the length of the returned object.

However, I believe in practice it's much faster, specially for repeated calls with same start_pos.

Example problem: https://leetcode.com/contest/weekly-contest-377/problems/minimum-cost-to-convert-string-ii/

Solution from contest winner below

const int N = 300;
const long long INF = 0x3F3F3F3F3F3F3FLL;

long long dis[N][N];

class Solution {
public:
    long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
        map<string, int> label;
        for (auto& v : original) {
            label[v];
        }
        for (auto& v : changed) {
            label[v];
        }
        int total = 0;
        for (auto& it : label) {
            it.second = total++;
        }
        
        for (int i = 0; i < total; ++i) {
            for (int j = 0; j < total; ++j) {
                dis[i][j] = INF;
            }
            dis[i][i] = 0;
        }
        
        for (int i = 0; i < original.size(); ++i) {
            int u = label[original[i]];
            int v = label[changed[i]];
            
            dis[u][v] = min(dis[u][v], (long long) cost[i]);
        }
        for (int k = 0; k < total; ++k) {
            for (int i = 0;i < total; ++i) {
                for (int j = 0; j < total; ++j) {
                    if (i != j && j != k && k != i) {
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                    }
                }
            }
        }
        
        vector<int> lens;
        for (auto& v : original) {
            lens.push_back(v.size());
        }
        sort(lens.begin(), lens.end());
        lens.erase(unique(lens.begin(), lens.end()), lens.end());
        
        int n = source.size();
        vector<long long> dp(n + 1, INF);
        dp[0] = 0;
        
        for (int i = 0; i < n; ++i) {
            if (source[i] == target[i]) {
                dp[i + 1] = min(dp[i + 1], dp[i]);
            }
            for (int l : lens) {
                if (i - l + 1 >= 0) {
                    string s = source.substr(i - l + 1, l);
                    string t = target.substr(i - l + 1, l);
                    auto u = label.find(s);
                    auto v = label.find(t);
                    if (u != label.end() && v != label.end()) {
                        dp[i + 1] = min(dp[i + 1], dp[i - l + 1] + dis[u->second][v->second]);
                    }
                }
            }
        }
        if (dp[n] >= INF) {
            return -1;
        }
        return dp[n];
    }
};

My analysis of the time complexity for the code above: I think substr() call should result in timeout. STL says complexity of substr(x, len) = len. Therefore, the dp loop is n * lens.size() * max_len where, n = source.size(), and max_len = max(lens[i]) for all i.

Eg. in the case where n = 1000, and we have lens = [900, 901, ..., 999]. Therefore,

1. Outer loop > for (int i = 0; i < n; ++i) n = 1000,

2. Inner loop > for (int l : lens), lens = [900, 901, ..., 999]

3. Inside inner loop. we call substr(st, l), in O(l). But max(l) = n

Thus, since max(l) = max_len = 999,

• Time Complexity = n * lens.size() * max_len

• Time Complexity = n * lens.size() * n

• Time Complexity = 1000*100*1000, which should TLE

There must be something going on making substr() more efficient. My guess is caching susbtr() calls so substr(i, x+d), uses previously queried substr(i, x),

Would love to understand more about the optimization going on in substr(). Or would this solution always give TLE for this test case, indicating that it could be hacked (even if not supported in Leetcode)?

Only thing I found is from https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring

I am working on Segment Trees, and more recently with this implementation by Al.Cash

He brings up this problem but even with the segment tree already built (I assume it stores the number of 'c's in a given range) I don't know how to answer the queries in O(logn). If it's all 'c's then it's easy but what if it's not? Some sort of divide and conquer?

I would appreciate some help with that problem, and recommendations for other good segment tree problems. Preferably on Codeforces (there is no segTree tag; data structures is the closest but it's no guarantee).

Thanks and have a good day!

As the title suggests, I submitted the identical source code, which in my environment and in c++17 gives the right answer, but in c++14 it gives WA. I am aware this usually involves some sort of default initialization, but I believe my codes does not rely on that. I appreciate your help and insights as to what might be happening!

WA

AC

Two editorials for this problem, but I followed this one