10508 - Word Morphing

[the LA-Z-BOy]

i used[c]char word[2500][2500][/c]still the judge shows 64kb used...
it's not the first time happened though.. when the program runs for little time (something like less than 1 millisecond) most of the cases it shows 64kb memory used. if the same program is permitted to run a bit longer, it would even show something like 1-10MB used... that's why most people ahead in the ranklist are shown 64kb mem used although space of the memory would be larger.
could somebody clarify this?

[Dominik Michniewski]

You have right. I think, that it's not fair for others, but I heard that is one of limitations of OJ system. when your program run faster than some time , that judge is not able to catch your memory usage properly. I don't know why - try to ask anyone from administrators - maybe they help you.

Best regards
DM

[babor]

I have got RTE: . Please say me array size .or give me some hints.

here is my code:-
/*
/* @JUDGE_ID: XXXXX 10508 C++ */
#include <stdio.h>
#include <string.h>

#define size 10000 // is it cover

char input[size][52];

bool morphed(char s1[], char s2[]);

void main()
{

int total,count,i,character;
char source[52];

while(scanf("%d %d",&total,&character)==2)
{

for(i=0;i<total;i++)
scanf("%s",input);

printf("%s\n",input[0]);

strcpy(source,input[0]);
count=1;

while(1)
{

if(count == total)
break;

for(i=0;i<total;i++)
{
if( strcmp(input,"") && morphed(source,input))
{


if(count == total)
break;
strcpy(source,input);
printf("%s\n",input);
strcpy(input,"");
count++;

}

}

}


}

}

bool morphed(char s1[], char s2[])
{

int match=0,len = strlen(s1),j;

for(j=0;j<len;j++)
if(s1[j] != s2[j])
match++;
if(match==1)
return true;

return false;

}

/*@END_OF_SOURCE_CODE*/


*/

[Yeomin]

number of words and number of letters are higher than 1000.

[tRipper]

If the number of words and the number of letters are both higher than 1000, how is it possible to solve this problem with brute force and checking words letter by letter? Time complexity is then O(n^3) which is (when n=1000) definetly too large to pass the time limit.

[mf]

You don't need brute force to solve the problem. There's a O(nm) algorithm.
Think about the given rules.

[tRipper]

There's a O(nm) algorithm.

You are right. I greatly underestimated this problem. Thanks.
AC now.

[soumit]

hi all,
I am getting WA in 10508. my approach is simple. i just calculate the distance of all the strings from the 1st string ( distance means the number of different letters between 2 strings ).

Then I output the given strings in increasing order of the distance from the the 1st string.

Now i am thinking whether the following input is a valid input and if it is the what should be the output coz my progm cannot handle this.

#INPUT:

5 3
dip
dop
sip
sop
sol


--
Soumit Salman

[Martin Macko]

No, the input is not valid.

2.- A letter can be changed just once
3.- All the letters in the word must change.

Thus, every letter have to be changed exactly once.

[smilitude]

my algo was simple;
1. at first i placed the second entry in the last;
2. then i did something like selection sort

loop till n
another loop
if the difference is one, i mean valid
then swap

then i managed a TLE for me,

Code: Select all

/*
 * 10508 word morphing
 * submission 1 RE 2 TLE
 * coded at 6:22 on 9th dec 05
 *
 */

#include <stdio.h>
#include <string.h>
#define MAX 1000

int diff(char *a, char *b) {
	int len=strlen(a);
	int count=0;
	for(int i=0;i<len;i++)
		if(a[i]!=b[i]) count++;
if(count==1) return 1;
return 0;
}

int main() {
	int m,n;
	int i,j;
	char words[MAX][201];
	char temp[201];

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

		for(i=0;i<m;i++)
			scanf("%s",words[i]);

		strcpy(temp,words[1]);
		strcpy(words[1],words[m-1]);
		strcpy(words[m-1],temp);

		for(i=0;i<m-1;i++)
			for(j=i+1;j<m-1;j++) {
				if(diff(words[i],words[j])) {
					if(j==i+1) break;
					strcpy(temp,words[i+1]);
					strcpy(words[i+1],words[j]);
					strcpy(words[j], temp);
					break;
				}
			}

		for(i=0;i<m;i++)
			printf("%s\n",words[i]);
	}
return 0;
}
	

tell me, what can i do?

[Mohammad Mahmudur Rahman]

The idea of sorting is alright. I used quick sort in this problem. Note that your sorting algorithm is something like O(m * m * sizeof(word)) which is large indeed.

[smilitude]

dearest,
thanks A LOTT for 343, i got ac there.
i indeed thought for quicksort, but i didnt know how to write that sort of compare_fuction, may be right now i can figure it out, but plz just tell me, what should i return if i think i need to sort, is it 1? i think its 1, else i will return 0 right? i think i am right. am i?

thanks a lot! really thanks a lott!

[Schutzstaffel]

You have to return -1 for "smaller than", 0 for "equals to" and 1 for "greater than", so to sort in an ascending order a must be smaller than b and in an descending order b must be smaller than a. See this example, hope it helps

[smilitude]

thanks a lot schutz!
but right at these problem, the compare function is bit of complex (at least to me! )
here i dont have a standard way to compare(like two int, i can just (a>b) return 1; (a<b) return -1; return 0;), i must put two objects at two end, then place the other things as "they just have a single letter difference with the preceding word", and i cannot gasp this idea for an algorithm like quick sort, what just divide the problem then conquare, not noticing what is the preceding.
yap! thats what i am asking now...

[Mohammad Mahmudur Rahman]

Umm, I think I'd better show you several patterns of compare_function to use with qsort() library function. Then you yourself will be able to pick what you actually need.

1. Just beginning from the scratch, suppose you want to sort

Code: Select all

 int a[10]; 

in ascending order.

Your compare function will be like this -

Code: Select all

int comp_func(const int *x,const int *y)
{
    return (*x - *y);
} 

2. Proceed on to sort

Code: Select all

char *str[10];

in descending order, you'll write -

Code: Select all

int comp_func(const char *x,const char *y)
{
    return (strcmp(y,x));
}

3. Now, consider this structure -

Code: Select all

struct data_
{
   int a,
   double b;
};

If you need to sort

Code: Select all

data_ dat[10];

such that it will be sorted in ascending order of a, & ties will be broken in descending order of b, your compare function will be something like this -

Code: Select all

int comp_func(const data_ *x,const data_ *y)
{
    if(x->a==y->a)
    {
         if(x->b > y->b)
             return -1;
         else if(x->b < y->b)
             return 1;
         else
             return 0;
     }
     else if(x->a > y->a)
         return 1;
     else
         return -1;
}