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 » Sat Oct 26, 2002 4:25 pm

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

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

Post by Christian Schuster » Sat Oct 26, 2002 5:57 pm

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 » Tue Oct 29, 2002 12:17 pm

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 » Tue Oct 29, 2002 4:59 pm

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 » Tue Oct 29, 2002 5:11 pm

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 » Tue Oct 29, 2002 8:46 pm

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 » Wed Oct 30, 2002 10:21 am

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 » Thu Oct 31, 2002 4:50 am

>>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 » Mon Nov 04, 2002 4:55 am

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 » Thu Dec 26, 2002 3:28 pm

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 » Sun Jan 05, 2003 11:36 am

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. » Thu Jan 09, 2003 11:10 am

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 » Fri Jan 10, 2003 10:06 am

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 » Tue Mar 11, 2003 9:41 am

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 » Wed Mar 12, 2003 7:53 am

Sort and binary search... gets me down to 0.22..

Post Reply

Return to “Volume 103 (10300-10399)”