10391 - Compound Words

[henar2]

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

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

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]

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]

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]

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

[henar2]

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

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

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]

eloha, what does your program output for:

a
aa
aaa
aaaa
aaaaa
aaaaaa

[eloha]

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

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]

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]

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

[Larry]

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