my code for longest common pattern(Problem code: LCPESY)......it is showing TLE..plz plz any one help 4 dat..........

help
, , ,
1

#include<string.h>

#include<stdio.h>

int main()
{
char a[10000],b[10000];

int t;

scanf("%d",&t);
  while(t>0)

{
int flag=0;

scanf("%s",&a);
scanf("%s",&b);
for(int i=0;i<strlen(a);i++)
{
	for(int j=0;j<strlen(b);j++)
	{
		if(a[i]==b[j]){
		flag++;
		b[j]='1';
		break;
	  }
	}
}
printf("%d",flag);

t--;

}

}

2

First of all, always remember that strlen() function is an O(n) function to calculate the length of a string. So, doing “for(i=0;i< strlen(a);i++)” makes the loop O(n^2) instead of O(n). Your two for loops were therefore performing O(n^4) to calculate the answer.
Now t is 100 and n is 1000 so that makes your solution O(tn^4) which is not possible to run in 1 sec.
Even making an O(tn^2) solution would give a TLE as it will be 10^10 which cannot be run in 1 sec.
The correct approach to the question is hashing. Have a look at this. It is the accepted version of your code.

2 Likes
3

Use Hashing bro. Basically using array indexes for fast access.

1 Like
4

how cn u calculate the program for in 1 sec or not,is just ur experience in the codechef or there is any sort of calculation regarding this,i undrstnd ur complexity bt cn u explain how does u calculate it for running in 1 sec or not

5

Its definitely experience. :slight_smile:
Most of the time it will work if your algorithm is not naive. The most basic approach is rarely the solution. (I am sorry i commented for roman28)

6

Request you to continue the discussion on the editorial page of the problem. Closing this question as of now.