OJ Board

Posted: **Sat Oct 26, 2002 4:25 pm**

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

Posted: **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.

Posted: **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.

Posted: **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.

Posted: **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.

Posted: **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."

Posted: **Wed Oct 30, 2002 10:21 am**

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

Posted: **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.

Posted: **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;
	}
}

Posted: **Thu Dec 26, 2002 3:28 pm**

eloha, what does your program output for:

a
aa
aaa
aaaa
aaaaa
aaaaaa

Posted: **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.

Posted: **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

Posted: **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!

Posted: **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

Posted: **Wed Mar 12, 2003 7:53 am**

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

OJ Board

10391 - Compound Words

10391 - Compound Words

maybe..

Re: maybe..