10282 - Babelfish

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

Moderator: Board moderators

mystical_liu
New poster
Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

10282 time limite exceeded~why?

Post by mystical_liu » Thu Sep 12, 2002 8:21 am

[cpp]
/* @JUDGE_ID: 6983KT 10282 C++ */
#include<stdio.h>
#include<string.h>
#define max 100000
typedef struct dict
{
char in[20],dic[20];
}dict;
dict arr[max];
long count=0;
main()
{
char in1[20],in2[20];
int i,j,k,flag;
while(gets(in1))
{
if(!strlen(in1))break;
j=0;
for(i=0;i<strlen(in1);i++)
{if(in1==' ')break;
else arr[count].in[j++]=in1;}
j=0;i++;
for(;i<strlen(in1);i++)
{if(in1=='\0')break;
else arr[count].dic[j++]=in1;}
count++;
}
for(i=0;i<20;i++)in1='\0';
while(gets(in1))
{
flag=0;
for(i=0;i<count;i++)
{
for(j=0;j<20;j++)in2[j]='\0';
strcpy(in2,arr.dic);
if(!(strcmp(in2,in1)))
{
printf("%s\n",arr.in);
flag=1; break;
}
}
if(!flag)printf("eh\n");
for(i=0;i<20;i++)in1='\0';
}
}[/cpp]
this is my code and the judgement says time limite exceeded~is there any method can solve this problem???

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Sep 12, 2002 8:32 am

I am not sure, that you handle input correctly ...
But try to use qsort and bsearch to find word in dictionary - this decrease complexity of search to log(num_words) from num_words ....

Dominik

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Sat Mar 29, 2003 6:38 am

I use Shell Sort and Binary Search to solve this problem.
I still need 9.4s to tackle it. I think optimization must be needed.

zzylhy
New poster
Posts: 6
Joined: Mon May 19, 2003 1:56 pm

10282

Post by zzylhy » Tue May 20, 2003 1:02 pm

#include<iostream.h>
#include<string.h>
#include<stdio.h>


class node
{
public:
node();
~node(){};
char s[10],t[10];
node *next;
};

node::node()
{
int i;
for(i=0;i<11;i++)
{
s='\0';
t='\0';
}
}

node *creat()
{
node *h,*p,*q;
char u[22],ch;
h=new node();
p=h;
while(1)
{
q=new node();
q->s[0]=getchar();
if(q->s[0]!=10)
{
scanf("%s",u);
strcat(q->s,u);
scanf("%s",q->t);
p->next=q;
p=p->next;
}
else
{
break;
}
ch=getchar();
}
p->next=NULL;
return h;
}

void select(node *h,char t[11])
{
node *p;
p=h;
while((p!=NULL)&&(strcmp(p->t,t)!=0))
{
p=p->next;
}
if(p==NULL)
cout<<"eh"<<endl;
else
puts(p->s);
}

int main()
{
node *head;
char t[11];
head=creat();
while(1)
{
gets(t);
if(t[0]=='\0')
break;
select(head,t);
}
return 0;
}

I got TimeLimitExceeded.
Is there another way to solve it?
:cry:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Aug 13, 2003 9:21 am

i haven't solved the problem but tried using avl tree and mapping of c++. it may help.
"Everything should be made simple, but not always simpler"

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10282 - Babelfish

Post by Riyad » Fri Aug 29, 2003 6:57 am

my code for 10282 is very simple , i pushed the words into a array of structure. and than searched the array of structure linearly . as a result it takes a long time to search . is there any way i can decrease the execution time of the program by using any efficient searching algorithm like binary search.pliiiiiiiiiiiiiiiiiz help. :cry: :cry: :cry: :cry: :cry: here is my code:

Code: Select all

#include<stdio.h>
#include<string.h>

struct dictionary{
	
	char word[15],meaning[25];

};

struct dictionary obj[100001];

long int index=0; 


int main(){

	char input[50];
	register long int i; 
	int flag;
	freopen("input.in","rt",stdin);
	while(gets(input)){
	
		if(strcmp(input,"")==0)
			break;
		sscanf(input,"%s %s",obj[index].meaning,obj[index].word);
		index++;
		
	}
	

	while(gets(input)){
		flag=0;
		for(i=0;i<index;i++){
			if(strcmp(obj[i].word,input)==0){
				flag=1;
				puts(obj[i].meaning);
				break;
			
			}
			else
				continue;
		}
		if(flag==0){
			puts("eh");
		}
	}
	
	
	return 0;
}
looking for u r help .
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Aug 29, 2003 7:09 am

Sort and binary search.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

still TLE plizzzzzzzzzzzzzzzzzzzzzzzz help

Post by Riyad » Fri Aug 29, 2003 5:53 pm

u told me to sort the arrays and binary search . i did as u said . but still i am having TLE . plizzzzzz help me in this prob :cry: :cry: :cry: :cry:
.here is my code:-

Code: Select all

#include<stdio.h>
#include<string.h>

struct dictionary{

	char word[15],meaning[25];

};

struct dictionary obj[100001];

long int index=0;
void sort(){
	register long int i ,j;
	struct dictionary temp;
	for(i=0;i<index;i++){
		for(j=i+1;j<index;j++){
			if(strcmp(obj[i].word,obj[j].word)>0){
				temp=obj[i];
				obj[i]=obj[j];
				obj[j]=temp;
			}
			else
				continue;
		}
	}

}
long int binsearch(char search[]){
	long int high,low,mid;
	
	low=0;
	high=index-1;
	while(low<=high){
		
		mid=(low+high)/2;

		if(strcmp(obj[mid].word,search)>0)
			high=mid-1;
		else if(strcmp(obj[mid].word,search)==0){
			
			return mid;
		}
		else
			low=mid+1;


	}
	
	return -1;


}


int main(){

	char input[50];
	long int bound;
	freopen("input.in","rt",stdin);
	while(gets(input)){

		if(strcmp(input,"")==0)
			break;
		sscanf(input,"%s %s",obj[index].meaning,obj[index].word);
		index++;

	}

	sort();
	
	while(gets(input)){
		
		bound=binsearch(input);
		if(bound!=-1){
			
			puts(obj[bound].meaning);
		}
		else{
			puts("eh");
		}
		
	}


	return 0;
}
Waiting for u r help . plizzzzzzzzz help.
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Aug 29, 2003 6:35 pm

You should read up on the qsort() function in C .. Quick sort is O(n log n) while bubble sort is O(n^2) which is much too slow for this problem.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

thanx

Post by Riyad » Fri Aug 29, 2003 6:56 pm

i got ac using qsort . thanx for u r help buddy .it took about 1.027 second which was really amazing .

hey friend need a little a favour . i am a novice in here . i got a code of prime generator but dont know how to use it . hope u ll help me using it .
here is the code:

Code: Select all

#include<stdlib.h>
#include<malloc.h>

#define isprime(f,x) (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define setprime(f,x) *(f+(x)/16)|=1<<(((x)%16L)/2)

void main()
{
unsigned char *field=NULL,*zzz;
unsigned long teste=1,max,mom,count,alloc;
int d;
max=20010000L;

while(field==NULL)
zzz=field=(unsigned char*) malloc(alloc=(((max-=10000L)>>4)+1L));

for (count=0;count<alloc;count++)
*zzz++ = 0x00;

while((teste+=2)<max)
if(!isprime(field,teste))
for(mom=3L*teste;mom<max;mom+=teste<<1)
setprime(field,mom);
	if(isprime(field,3)==1)
/*now you can cll the module isprime to check any positive integer 
either prime or not; 
syntax: 
isprime(field,integer); 

if the module return 0 the integer will be prime 
else not prime. 

you can check upto 20000000 within a while 
*/ 

free (field); 
}
** my question is what will i use in place for field while calling the function isprime(). i understood that i ll use the integer which primality i am gonna check in place of the isprime(field,integer).give me an example plizzzzzzzzzzzzzzz.
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

10282

Post by Sanny » Fri Jul 30, 2004 1:35 am

Hello,
I've encountered a funny incident which I can not explain.

See the two codes of problem no 10282:

This got accepted :

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define size 100005

struct dictionary
{
char foreign[12];
char eng[12];
}dict[size],*ptr;


int sort_f(const dictionary *a,const dictionary *b)
{
return (strcmp(a->foreign,b->foreign));
}


int main()
{
long int total=0;
char line[1000],temp[200];

while(gets(line))
{
if(line[0]=='\0')
break;

sscanf(line,"%s %s",dict[total].eng,dict[total].foreign);
total++;
//note the second code
}
qsort(dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

while(gets(temp))
{

ptr=(dictionary *)bsearch(temp,dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

if(ptr)
printf("%s\n",(*ptr).eng);
else
printf("eh\n");

}

return 0;
}
[/cpp]

But this one didn't :oops: :

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define size 100005

struct dictionary
{
char foreign[12];
char eng[12];
}dict[size],*ptr;


int sort_f(const dictionary *a,const dictionary *b)
{
return (strcmp(a->foreign,b->foreign));
}


int main()
{
long int total=0;
char line[1000],temp[200];

while(gets(line))
{
if(line[0]=='\0')
break;
sscanf(line,"%s %s",dict[total].eng,dict[total++].foreign);
//here's the only change
}
qsort(dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

while(gets(temp))
{

ptr=(dictionary *)bsearch(temp,dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

if(ptr)
printf("%s\n",(*ptr).eng);
else
printf("eh\n");

}

return 0;
}
[/cpp]

Can anyone explain it??? :cry:

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Jul 30, 2004 6:29 am

Code: Select all

sscanf(line,"%s %s",dict[total].eng,dict[total++].foreign);
In your code, you want the "++" operation to be executed after "total" is evaluated for twice. However, in the ANSI standard, it is not defined when will "++" operation executed in such statement.
The behaviour of such statment is compiler dependent.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Fri Jul 30, 2004 10:50 am

.. wrote:

Code: Select all

sscanf(line,"%s %s",dict[total].eng,dict[total++].foreign);
In your code, you want the "++" operation to be executed after "total" is evaluated for twice. However, in the ANSI standard, it is not defined when will "++" operation executed in such statement.
The behaviour of such statment is compiler dependent.
I think that Sanny was misleaded by the fact that side-effect are guaranteed to be completed after a sequence-point.
A sequence point is defined as:
  • * The call to a function, after the arguments have been evaluated.

    * The end of the first operand of the following operators: logical AND &&; logical OR ||; conditional ? ; comma , .

    * The end of a full expression: an initializer; the expression in an expression statement; the controlling expression of a selection statement (if or switch); the controlling expression of a while or do statement; each of the three expressions of a for statement; the expression in a return statement.
In his piece of code the sequence point at which the postdecrement of the variable total is completed is the call of the function sscanf. Athough there are commas between the variables passed to sscanf these *cannot* be considered as the "comma operator", hence the confusion.

Ciao!!!

Claudio

someone
New poster
Posts: 2
Joined: Mon Aug 30, 2004 9:00 am

10282 TLE

Post by someone » Sun Sep 05, 2004 9:38 am

ok, the code below is very simple, why do I get TLE for this

[cpp]#include <cstdio>
#include <map>
#include <string>
#include <iostream>
using namespace std;

map <string,string> rijecnik;
map <string,string>:: iterator iter;

char buffer[1000],ch[500],ch2[500];

int main ()
{
while (fgets(buffer,1000,stdin))
{
if (buffer[0]=='\n')break;
sscanf(buffer,"%s%s",ch,ch2);
rijecnik[ch]=ch2;
};
while (fgets(ch,1000,stdin))
{
sscanf(ch,"%s",buffer);
iter = rijecnik.find(buffer);
if (iter!=rijecnik.end())cout<<iter->second<<'\n';else cout<<"eh\n";
};
return 0;
};[/cpp]

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

10282-why RTE

Post by sunny » Sun Sep 25, 2005 10:39 pm

some1 please explain me why i m gettin RTE for 10282. i didn't used the built-in bsearch here.
Last edited by sunny on Thu Oct 26, 2006 11:02 pm, edited 1 time in total.

Post Reply

Return to “Volume 102 (10200-10299)”