How can this be a TLE?

Hi Everyone, I was solving a problem and i’m constantly getting TLE, which is confusing to me as i’m pretty sure my algorithm is of the complexity O(T*r*c*log(r*c))

Here the constraints are (taken from the problem page)

T ≤ 100
2≤r,c≤100

So i am guessing a somewhat 10^6 computations in worst case which should be fine for a Time Limit of 1 sec? but i get TLE.

Can someone tell me what am i doing wrong? I am simply traversing a matrix and building an adjacency list .

TLE Code

``````
#include <bits/stdc++.h>
using namespace std;
# define int long long
#define F first
#define S second
#define pii pair<int,int>
#define INF LONG_MAX

int node(int i,int j,int c){
return i*c + j+1;
}

int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int t;
cin >> t;

while(t--){
int r,c,x1,y1,x2,y2;
cin >> r >> c >> x1 >> y1 >> x2 >> y2;

char grid[r][c];

for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin >> grid[i][j];
}
}

int cost[r*c+5][r*c+5];
memset(cost,0,sizeof cost);
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
int node1=node(i,j,c);
if(i+1<r){
int node2=node(i+1,j,c);
if(grid[i+1][j]=='1'){
cost[node1][node2]=1;
}
}

if(j+1<c){
int node2=node(i,j+1,c);
if(grid[i][j+1]=='1'){
cost[node1][node2]=1;
}
}

if(i-1>=0){
int node2=node(i-1,j,c);
if(grid[i-1][j]=='1'){
cost[node1][node2]=1;
}
}

if(j-1>=0){
int node2=node(i,j-1,c);
if(grid[i][j-1]=='1'){
cost[node1][node2]=1;
}
}
}
}

}
return 0;
}

``````
1 Like

Hi, I tested the code locally, it turned out that the size of the cost array is too big when r = c = 100,
so you must declare it as global array (that’s what my “codeblocks” says).

even if it worked, imagine 100 test cases of the worst case scenario (r = 100 , c = 100) and in every test case you are doing memset to the cost array which has size of (r * c * r * c), then it will be TLE for sure: 100 * rc * rc = 10^10.

note: I’m not sure about memset complexity but it costed me TLE a couple of times and I had to get rid of it.

2 Likes

Oh shoot ! Thanks buddy, I just realised the same, thanks for helping me out

2 Likes