You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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--;

}

}

asked 03 May '14, 18:47

k1k1313's gravatar image

1★k1k1313
1014
accept rate: 0%

closed 23 Jun '14, 22:10

admin's gravatar image

0★admin ♦♦
19.8k350498541

The question has been closed for the following reason "Duplicate Question" by admin 23 Jun '14, 22:10


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(t
n^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.

link

answered 04 May '14, 00:02

roman28's gravatar image

4★roman28
1.6k71429
accept rate: 19%

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

(05 May '14, 16:50) k1k13131★

Its definitely experience. :) 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)

(05 May '14, 21:40) princelegolas2★

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

link

answered 04 May '14, 00:18

princelegolas's gravatar image

2★princelegolas
25513
accept rate: 15%

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

link

answered 23 Jun '14, 22:10

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,716
×717
×20
×19

question asked: 03 May '14, 18:47

question was seen: 935 times

last updated: 23 Jun '14, 22:10