## 10508 - Word Morphing

Moderator: Board moderators

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

### 10508 - Word Morphing

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!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
My accepted program assume there is at most 2000 words~~
Check if you do anything wrong~
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

### Re: 10508-Word Morphing ,runtime error!

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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 ?
[]s
Mauricio Oliveira Carneiro

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

### Why this code got wrong answer?

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]
Retired from SJTU Accelerator 2004

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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
``````
Greetings...
Istiaque Ahmed [the LA-Z-BOy]

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China
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?

I don't know how I can get string "ada".
Retired from SJTU Accelerator 2004

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China
Hi,Even.

I have changed 1000 into 2000,but still got Wrong Answer.
Do you think my algorithm is OK?
Retired from SJTU Accelerator 2004

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
hujialie wrote:Hi,Even.

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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
[]s
Mauricio Oliveira Carneiro

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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.
[]s
Mauricio Oliveira Carneiro

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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.
Istiaque Ahmed [the LA-Z-BOy]

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China
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.
Retired from SJTU Accelerator 2004