10391 - Compound Words

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

Moderator: Board moderators

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

10391 - Compound Words

Post by henar2 »

Please, could somebody post some conflictive inputs and outputs?
Thank you.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster »

I think the main problem is the time limit. If you get WA, it's probably better to briefly describe your algorithm here. We might then be able to discuss and post some counterexamples.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 »

I get WA every time I send the problem.

My algorithm:
For each word I look for every other word with the root equal to that word, then I get
the tail of that word and I search if that tail exists as a unique word and i check if it is
not the root to avoid false compound words made using the same word twice.

I don't understand what is wrong.
Thank you.

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse »

I think a compound word can be made using the same word twice. My AC program got WA after I added a statement to omit this case.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 »

Thank you. But I don't think that the problem statement is right because it says
that must be two different words. Anyway it was accepted.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

While I agree that the statement isn't all that clear, it does not say "two different words."

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 »

I thought that saying "two other words" meant "two different words".

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm

Post by hongping »

>>I thought that saying "two other words" meant "two different words".

I thought so too, and kept getting WA. I changed my program to be able to use the same word twice to create another word. Finally AC.

I agree that the question statement is misleading.

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha »

I think my algorithm is ok, but I got WA.
Can anyone help check my code or give me some sample input?

Code: Select all

for(n=0; gets(w[n]); n++);
for(i=0; i<n; i++)
{
	wilen=strlen(w[i]);
	for(j=i+1; j<n ;j++)
	{       wjlen=strlen(w[j]);
		if(wjlen>wilen)
		{
			for(k=impossible=0; k<wilen; k++)
				if(w[j][k]!=w[i][k]) { impossible=1; break;}
			if(impossible) break;
			for(k=wilen, index=0; k<wjlen; k++) s[index++]=w[j][k];
			s[index]='\0';
			itemptr=(char *) bsearch(s,w,n,sizeof(w[0]),compare_function);
			if(itemptr) printf("%s\n",w[j]);
		}
		else break;
	}
}

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

eloha, what does your program output for:

a
aa
aaa
aaaa
aaaaa
aaaaaa

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha »

Caesum wrote:eloha, what does your program output for:

a
aa
aaa
aaaa
aaaaa
aaaaaa
My program output:

Code: Select all

aa
aaa
aaaa
aaaaa
aaaaaa
aaa
aaaa
aaaaa
aaaaaa
aaaa
aaaaa
aaaaaa
aaaaa
aaaaaa
aaaaaa
After adding an array to prevent printing a word twice, my output is:

Code: Select all

aa
aaa
aaaa
aaaaa
aaaaaa
Is that correct? I still get WA. :(

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

maybe..

Post by Whinii F. »

I experienced the same problem today, and solved it by not producing the output directly. I marked the compound words and printed it later in order then I got AC instead of WA.

Maybe your code doesn't guarantee to make output in order, too.
Try :)

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Re: maybe..

Post by eloha »

Whinii F. wrote:I experienced the same problem today, and solved it by not producing the output directly. I marked the compound words and printed it later in order then I got AC instead of WA.

Maybe your code doesn't guarantee to make output in order, too.
Try :)
Whinii F. Thank you so much!
I got AC now! :D

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

Post by Dominik Michniewski »

I got Acc , when I try to solve this problem, but how can I improve efficiency of my code ? Which algorithm can solve this problem with less than 0.5 sec ? I got time 2.1 sec ....

Thanks for explanation
Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

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... gets me down to 0.22..

Post Reply

Return to “Volume 103 (10300-10399)”