How can this be a TLE?

general
1

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];
			}
		}
		
		set<int> adj[r*c+5];
		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);
					adj[node1].insert(node2);
					adj[node2].insert(node1);
					if(grid[i+1][j]=='1'){
						cost[node1][node2]=1;
					}
				}
				
				if(j+1<c){
					int node2=node(i,j+1,c);					
					adj[node1].insert(node2);
					adj[node2].insert(node1);
					if(grid[i][j+1]=='1'){
						cost[node1][node2]=1;
					}
				}
				
				if(i-1>=0){
					int node2=node(i-1,j,c);										
					adj[node1].insert(node2);
					adj[node2].insert(node1);
					if(grid[i-1][j]=='1'){
						cost[node1][node2]=1;
					}
				}
				
				if(j-1>=0){
					int node2=node(i,j-1,c);					
					adj[node1].insert(node2);
					adj[node2].insert(node1);
					if(grid[i][j-1]=='1'){
						cost[node1][node2]=1;
					}
				}
			}
		}
	
	}    
	return 0;
}
1 Like
2

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
3

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

2 Likes