11362 - Phone List

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

11362 - Phone List

Post by Ron » Sun Dec 30, 2007 8:25 pm

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
Last edited by Ron on Sun Dec 30, 2007 11:00 pm, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Dec 30, 2007 10:08 pm

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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11362 - Phone List

Post by Chirag Chheda » Wed Jul 02, 2008 8:24 am

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

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11362 - Phone List

Post by kbr_iut » Mon Aug 18, 2008 4:18 am

yes,u r right. u have to sort those numbers and then just check one number and between next number.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11362 - Phone List

Post by kbr_iut » Tue Aug 19, 2008 3:51 pm

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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

bleedingeyes
New poster
Posts: 9
Joined: Thu Aug 21, 2008 3:08 am
Location: IUT

Re: 11362 - Phone List

Post by bleedingeyes » Thu Oct 09, 2008 12:46 am

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

wanna be notorious....

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11362 - Phone List

Post by Obaida » Thu Nov 13, 2008 6:59 am

1'st sort the values in an efficient way. Then do it. :wink:
try_try_try_try_&&&_try@try.com
This may be the address of success.

setu
New poster
Posts: 4
Joined: Fri Mar 06, 2009 11:33 pm

Re: 11362 - Phone List

Post by setu » Wed Apr 22, 2009 1:13 pm

bleedingeyes wrote: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
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11362 - Phone List

Post by Jehad Uddin » Sun Aug 30, 2009 5:49 pm

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

Mahabub Khan
New poster
Posts: 5
Joined: Sun Apr 08, 2012 5:36 pm

Re: 11362 - Phone List

Post by Mahabub Khan » Tue Oct 30, 2012 7:15 pm

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 :)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11362 - Phone List

Post by sohel » Tue Oct 30, 2012 8:26 pm

Who said we are sorting each number?

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 11362 - Phone List

Post by triplemzim » Sun Aug 18, 2013 10:34 pm

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
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 11362 - Phone List

Post by triplemzim » Sun Aug 18, 2013 10:37 pm

setu wrote:
bleedingeyes wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11362 - Phone List

Post by brianfry713 » Mon Aug 19, 2013 10:23 pm

Sort as strings not as integers.
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 11362 - Phone List

Post by triplemzim » Tue Aug 27, 2013 2:01 am

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

Post Reply

Return to “Volume 113 (11300-11399)”