10508 - Word Morphing

sunhong · Post by **sunhong** » Tue Jun 17, 2003 6:25 am

The description of this problem include:The number of words are unlimited! But I don't know how many words there are in one case at most. I've used array of 10000 to store the words but got runtime error! Please help me, thank you!

.. · Post by .. » Tue Jun 17, 2003 9:28 am

My accepted program assume there is at most 2000 words~~
Check if you do anything wrong~

Even · Post by **Even** » Wed Jun 18, 2003 6:29 pm

sunhong wrote:The description of this problem include:The number of words are unlimited! But I don't know how many words there are in one case at most.

One method, you can use malloc, because first line of each case will tell you how many words and how long of each word.

But, since the problem descript that "The number of words are unlimited!"

If there is any method needn't use so large memory?
or is there any method needn't care about the number of words ?

you can think about it, good luck

carneiro · Post by **carneiro** » Thu Jun 19, 2003 1:38 am

I've thinked a lot trying to find a way to do this problem without caring about the number of words, but I couldn't find any.

I coded with mallocs ... no problems with that, and I made a dfs to find the solution. It's ok , but I got TLE .

I optimized it with a matrix pre calculating the distances of each word, thus skipping unfeasible changes, but I still got TLE.

How did you guys got accepted ?

Even · Post by **Even** » Thu Jun 19, 2003 1:01 pm

carneiro wrote:I've thinked a lot trying to find a way to do this problem without caring about the number of words, but I couldn't find any.

I coded with mallocs ... no problems with that, and I made a dfs to find the solution. It's ok , but I got TLE .

I optimized it with a matrix pre calculating the distances of each word, thus skipping unfeasible changes, but I still got TLE.

How did you guys got accepted ?

Each letter should be changed and can only be changed once

you can try to think WHEN a letter be changed

you needn't use dfs. and needn't calcaulte all the distances between each word.

you can just to compare with the original one.

hujialie · Post by **hujialie** » Tue Jul 01, 2003 1:47 pm

I just scan the intermediate word for how many different characters it has,
compared with the original one,and output them.But I got Wrong Answer,
why?Can anyone tell me the reason,or give me some input data?

Thank you indeed.

[c]#include "stdio.h"
#include "string.h"

char word[1000][1000];

int main()
{
int m,n,dif,i,j;
char temp[1000];
while(scanf("%d%d",&m,&n)==2)
{
scanf("%s",word[0]);
for(i=1;i<m;i++)
{
scanf("%s",temp);
dif=0;
for(j=0;j<n;j++)if((word[0][j]!=temp[j])&&(word[0][j]!=temp[j]+32)&&(word[0][j]!=temp[j]-32))dif++;
strcpy(word[dif],temp);
}
for(i=0;i<m;i++)printf("%s\n",word);
}
return 0;
}[/c]

the LA-Z-BOy · Post by **the LA-Z-BOy** » Tue Jul 01, 2003 2:18 pm

i think you misunderstood the problem.
are you thinking that always number of words = number of letters+1 ? your program is only okay at that particular case... but the problem didn't say that... so the input might look like...

Code: Select all

10 3
abc
def
abf
abg
cdb
dbc
dbf
aec
aef
ada

Greetings...

hujialie · Post by **hujialie** » Tue Jul 01, 2003 2:42 pm

Hello, the LA-Z-BOy.

I was just thinking of the problem like you wrote.
number of words = number of letters+1

for the problem has this sentence:

2.- A letter can be changed just once

So I think number of words = number of letters+1;
According to your saying, what does this sentence mean?

And,what's output for your input?
I don't know how I can get string "ada".

Even · Post by **Even** » Tue Jul 01, 2003 3:03 pm

Hello, hujialie

try to declare more large, such as word[2000][2000]

Hello, LA-Z-BOy

the case you give will not happen.
you can read the problem description one more time.

hujialie · Post by **hujialie** » Tue Jul 01, 2003 3:57 pm

Hi,Even.

Thank you for your reply.
I have changed 1000 into 2000,but still got Wrong Answer.

Do you think my algorithm is OK?

Even · Post by **Even** » Tue Jul 01, 2003 5:30 pm

hujialie wrote:Hi,Even.

Thank you for your reply.
I have changed 1000 into 2000,but still got Wrong Answer.
Do you think my algorithm is OK?

mm... you should treat capital one and lowercase letter as different

It means that if( word[0][j] != temp[j] ) diff++

carneiro · Post by **carneiro** » Tue Jul 01, 2003 9:19 pm

2.- A letter can be changed just once

This doesn't mean that you'll have to use ALL THE WORDS of the input. It just means that you'll have to use N of them. (be n the number of letters in the word) .

The input can be like that of LA-Z-BOy

carneiro · Post by **carneiro** » Tue Jul 01, 2003 9:47 pm

Alright, I'm just bitting my tong here...

I've recoded everything without carying about the number of words, doing as hujialie said, and finally got accepted with a 9 lines C code.

I believe this problem is not quite well written ... for this line should be : ALL THE WORDS IN THE INPUT SHALL BE USED.

Or just take out the "w" parameter of the input since it'll always be n+1.

Hope this helps everyone.

the LA-Z-BOy · Post by **the LA-Z-BOy** » Wed Jul 02, 2003 12:01 am

damn... i thought the problem was harderer.... but in fact it is not... i now understand why this prob took 8sec+ for me to get AC

carneiro wrote:I believe this problem is not quite well written ... for this line should be : ALL THE WORDS IN THE INPUT SHALL BE USED.

you are right... the problem description never wrote that number of words = number of letters+1 but in fact it is true for the problem

dear hujialie, sorry for misguiding you anyway

, really really sorry.
thanks hujialie, carneiro, Even; thanks everybody...goodluck...
ps. now i've changed my code, and got at in 0.061 sec.

hujialie · Post by **hujialie** » Wed Jul 02, 2003 11:16 am

Thank all of you.Now I have got Accepted.
But I am still interested to know how to do it
without using a memory of n*n.I saw a lot of
people using just 64KB.

OJ Board

10508 - Word Morphing

10508 - Word Morphing

Re: 10508-Word Morphing ,runtime error!

Why this code got wrong answer?