10508 - Word Morphing

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10508 - Word Morphing

Post by sunhong »

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

Post by .. »

My accepted program assume there is at most 2000 words~~
Check if you do anything wrong~
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    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!

Post by Even »

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 :wink:

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro »

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

Post by Even »

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?

Post by hujialie »

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
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

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...
Istiaque Ahmed [the LA-Z-BOy]

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie »

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

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

Post by Even »

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

Post by hujialie »

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

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

Post by Even »

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

Post by carneiro »

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:

Post by carneiro »

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
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

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

Post by hujialie »

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

Post Reply

Return to “Volume 105 (10500-10599)”