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

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

10508. Word morphing. ---Getting Output Limit Exceeded

Post by shihabrc »

Hi all,

I've tried to solve this problem by:
1.computing the distance of the words frm the 1st word.
2. Sort(ascending) the words on the basis of the distances and output them all.

But, i'm getting OLE. I don't know why. Can someone help me with some suggetions. And is anything wrong in my approach.

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct Word{
	char word[1005];//edited after AC
	int d;
} Word;

Word word[1005];//edited after AC

int comp(const void* a, const void *b){
	Word* x=(Word*) a;
	Word* y=(Word*) b;

	return x->d - y->d;
}

void main(){
	int i,j,m,n;

//	freopen("C:\\4.txt","r",stdin);

	while(scanf("%d %d",&m,&n)==2){
		getchar();

		for(i=0;i<m;i++){
			word[i].d=0;
			gets(word[i].word);
			for(j=0;j<n;j++) if(word[0].word[j]!=word[i].word[j]) word[i].d++;
		}

		qsort(word,m,sizeof(Word),comp);

		for(i=0;i<m;i++) puts(word[i].word);
	}
}


-Shihab
Last edited by shihabrc on Sat Apr 29, 2006 4:35 pm, edited 1 time in total.
Shihab
CSE,BUET

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Your approach is alright. Are you sure you're getting OLE?

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc »

Ya, I got OLE in the first 2 submissions. But, today when i made a 3rd submission (with the same code) I got WA. After changing some array size I finally got AC. But , it took too much memory. I saw that a lot of ppl hav solved it with very low memory spent. How can I optimize the space complexity. And, i think this prob can also be solved with BFS(this prob has very much similarity with prob 429). If i'm wrong correct me.

-Shihab
Shihab
CSE,BUET

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

heh, I am getting PE for this problem....I don;t see anything tricky about the formatting, you're just outputting the words (and I preserved all upper/lower cases).

Any ideas?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

I see that the above posted code gets AC, so I am guessing from 'a' to 'A' is considered a change as well?

I thought changing means changing the letter to a different alphabet....

sujon
New poster
Posts: 5
Joined: Thu Aug 28, 2008 4:17 pm

RE,RE,RE why ? anyhbody please help me.

Post by sujon »

Code: Select all


#include<iostream.h>
#include<stdio.h>
#include<string.h>
#define max 25000

	   // #include<conio.h>

int main()
{
			 //   clrscr();

char word[max][max],input[max];
char w[max],mor[max];

long int n,l,i,count,j;

//freopen("input.txt","r",stdin);
while(gets(input))
{

sscanf(input,"%ld %ld",&n,&l);

gets(w);
gets(mor);

for(j=0;j<n-2;j++)
{

gets(input);

   count=0;

 for(i=0;i<l;i++)
  if(input[i]!=w[i])
   count++;

 strcpy(word[count-1],input);
}


puts(w);

for(i=0;i<l-1;i++)
puts(word[i]);
puts(mor);

}

return 0;
}


Post Reply

Return to “Volume 105 (10500-10599)”