11362 - Phone List

[Ron]

why im getting TLE....

My Code :

Code: Select all

#include<iostream>
#include<string>
using namespace std;
int main(){
	int t,n,i;
	string v[10000];
	int size[10000];
	cin>>t;
	while(t--){
		cin>>n;
		string s;
		bool flag=1;
		cin>>v[0];
		size[0]=v[0].length();
		n--;
		i=1;
		int j;
		while(n--){
			cin>>v[i];
			if(flag){
				size[i]=v[i].length();
				for(j=0;j<i;j++){
					if(flag){
						if(size[i]>size[j]){
							if(v[i].substr(0,size[j])==v[j]){
								flag=0;
								break;
							}
						}
						else{
							if(v[j].substr(0,size[i])==v[i]){
								flag=0;
								break;
							}
						}
					}
				}
			}
			i++;
		}
		if(flag)	cout<<"YES\n";
		else	cout<<"NO\n";
	}
	return 0;
}

please check my code...........................
what should i do ????


EDIT : Thnx sohel !! Now i got accepted ....

Title edited by moderator

[sohel]

An O(n^2) algorithm for this problem will get TLE.

Think of how you can reduce the runtime to O(n log n)?

[Chirag Chheda]

Even i m getting TLE.
can neone who has got ACC jus tell me whether i should sort the numbers on the basis of their length and then start searching..
Thnx in advance.

Waiting for a reply..

[kbr_iut]

yes,u r right. u have to sort those numbers and then just check one number and between next number.

[kbr_iut]

dont post ambiguous topic.
here all posts r about volume 113.
if u want to post something interesting or like that there is appropriate position for it,,,general chit-chat
http://online-judge.uva.es/board/viewforum.php?f=24
dont do this again.

[bleedingeyes]

why i am getting TLE
please help

Code: Select all

#include<stdio.h>
#include<algorithm>

using namespace std;

struct tag
{
	char data[15];
	int len;
}num[10050];

bool cmp(const tag &p,const tag &q)
{
	return p.len<q.len;
}

int main()
{
	int a,b,i,j,k,flag;


//	freopen("in.txt","r",stdin);

	while(scanf("%d",&a)==1)
	{
		for(k=0;k<a;k++)
		{
			scanf("%d",&b);

			flag=0;

			for(i=0;i<b;i++)
			{
				scanf("%s",&num[i].data);
				num[i].len=strlen(num[i].data);
			}

			sort(num,num+b,cmp);

			for(i=0;i<b-1;i++)
			{
				if(flag) break;
				for(j=i+1;j<b;j++)
				{
					if(num[i].len>num[j].len) break;
					else if(i==j) continue;
					else
					{
						const char* p = search(num[j].data, num[j].data + num[i].len, num[i].data, num[i].data + num[i].len);
						if((p-num[j].data)==0)
						{
							flag=1;
							break;
						}

					}
				}
			}

			if(flag)
				printf("NO\n");
			else
				printf("YES\n");

		}
	}

	return 0;
}

[Obaida]

1'st sort the values in an efficient way. Then do it.

[setu]

why i am getting TLE
please help

First find out the sorted form of strings in O(nlgn) time . U can sort it by qsort too.
Then scan previous and next string to find if the previous string is a substring of next string.
Hope it will help...
##############################################
I have expressed my thought from my little knowledge.

[Jehad Uddin]

thank u setu vai for ur post,it really helps to get accepted

[Mahabub Khan]

why we sort
the array?
if we sort this

3
911
97625999
91125426

then it becomes

119
25679999
11224569

answer should be "Yes"
please anyone describe this.

Thanks in advance

[sohel]

Who said we are sorting each number?

[triplemzim]

Why getting TLE please help???
here is my code...

Code: Select all

#include<iostream>
#include<cstdio>
#include<math.h>
#include<string.h>

using namespace std;
int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}

int main()
{
    char ch[10009][11];
    int cases,n;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",ch[i]);
        }
        int flag=1;
        for(int i=0;i<n-1;i++)
        {
            int ilen=strlen(ch[i]);
            for(int j=i+1;j<n;j++){
                int len=min(ilen,strlen(ch[j]));
                flag=1;
                for(int k=0;k<len;k++)
                {
                    if(ch[i][k]!=ch[j][k])
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;

        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

[triplemzim]

why i am getting TLE
please help

First find out the sorted form of strings in O(nlgn) time . U can sort it by qsort too.
Then scan previous and next string to find if the previous string is a substring of next string.
Hope it will help...
##############################################
I have expressed my thought from my little knowledge.

I didn't understand your logic... if we sort this input ( 911,9101,911234) then how can we find if it is consistent by checking just with the previous one???

[brianfry713]

Sort as strings not as integers.

[triplemzim]

yup got it!!!! it's called lexicographical sorting