## 10391 - Compound Words

Moderator: Board moderators

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am

### 10391 - Compound Words

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

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
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
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:
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
I thought that saying "two other words" meant "two different words".

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm
>>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
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:
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
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..

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

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!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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:
Sort and binary search... gets me down to 0.22..