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 »

[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 »

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 »

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 »

#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 »

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 »

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 »

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 »

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

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

Post by UFP2161 »

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 »

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 »

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

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 »

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

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 »

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