Page 2 of 6

Posted: Fri Sep 02, 2005 1:41 pm
by Nazmul Quader Zinnuree
Somebody help me know...
Every word is reachable from every other words ?? How ??
or, the pairs of words will always be of same length ??
bfs can be used to solve it ??
multiple input need to output "Case no" for every set of output ?? or just to take input for no of test cases...??

429 - TLE

Posted: Thu Sep 21, 2006 10:42 am
by Donotalo
getting TLE in 429. my code is written in C++. can anyone give me large input and output for this problem?

200 words in the dictionary. besides, i'm using map to use this words. so it shud not take too much time. my program passes successfully sample test case. please help me!

Posted: Sat Mar 17, 2007 8:09 am
by kolpobilashi
i am getting WA for this problem
http://acm.uva.es/p/v4/429.html
anyone can help...?? :(

Code: Select all

cut..
thanx in advance..

Posted: Sat Mar 17, 2007 12:55 pm
by Jan
Replace the 'main' function...

Code: Select all

Removed...
Minor changes, so no big deal. Hope it helps.

Posted: Sat Mar 17, 2007 3:22 pm
by kolpobilashi
That's it !!! :o :o
thanx Jan... :)

Posted: Thu Jun 21, 2007 4:25 pm
by kn
I use binary search and 2D array to implement...
Y WA...?

Code: Select all

AC-ed
I read the question wrong again.. :( 

Posted: Thu Jun 21, 2007 7:07 pm
by ayeshapakhi
hello...

i didn't see ur code...but ur program gives output for

Code: Select all

2

aaa
bbb
aab
aba
abb
a
b
*
aab bbb

abc
abd
aaa
aab
abb
*
abb aab
abc abd
aab bbb

Code: Select all

aab abb 1

abb aab 1
abb abb 0
aab abb 1
:roll: is it correct??

Posted: Thu Jun 21, 2007 7:55 pm
by kn
ayeshapakhi wrote:hello...

i didn't see ur code...but ur program gives output for

Code: Select all

2

aaa
bbb
aab
aba
abb
a
b
*
aab bbb

abc
abd
aaa
aab
abb
*
abb aab
abc abd
aab bbb

Code: Select all

aab abb 1

abb aab 1
abb abb 0
aab abb 1
:roll: is it correct??
Well... in your test case, words are not in a lexicographical order, which is assumed in the specification of the problem
I did take this assumption in solving the problem



Sorry for that, I was wrong

Posted: Thu Jun 21, 2007 9:58 pm
by Jan
kn wrote:Well... in your test case, words are not in a lexicographical order, which is assumed in the specification of the problem
I did take this assumption in solving the problem
Read the description again...
all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.
Words can appear in any order. So, your assumption is wrong. Hope it helps.

Posted: Fri Jun 22, 2007 12:37 pm
by kn
Jan wrote:
kn wrote:Well... in your test case, words are not in a lexicographical order, which is assumed in the specification of the problem
I did take this assumption in solving the problem
Read the description again...
all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.
Words can appear in any order. So, your assumption is wrong. Hope it helps.
o...really...
how comes...thx Jan, I'm now trying
AC-ed...thx

Posted: Sat Oct 20, 2007 11:58 am
by sapnil
Hi i am trying with BFS,but WR
Is there any tricky case?

Thanks
Keep posting
Sapnil

Re: 429 - Word Transformation

Posted: Sat Nov 01, 2008 9:12 am
by deadangelx
Sample Input

Code: Select all

4

dip
lip
mad
map
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

dip
lip
mad
map
mapl
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice slick
may mad
map maple
maple map
map map

mapl
maple
mba
mbal
mbale
mbple
*
mba mapl

map
mapl
maple
mba
mbal
mbale
mbp
mbple
*
mba mapl
Sample Output

Code: Select all

spice stock 4
may pod 3

spice slick 2
may mad 1
map maple 2
maple map 2
map map 0

mba mapl 5

mba mapl 3

429 - Word Transformation

Posted: Sat Dec 26, 2009 10:31 am
by gt1404
Hey guys I'm wondering if anyone can offer some advice on this problem. I'm new to the site (solved about ~10). I submitted this specific problem multiple times under multiple white space interpretations. I'm fairly confident that my algorithm works and it passes all test cases. So I am wondering if anyone has ran into similar difficulties here that they care to share.

Also regarding the problem I count spaces as a letter meaning:
"a" can be changed to "ba" and "ab" legally

I think I might have some sort of whitespace issues?. Also I am running g++ under cygwin in windows (unix style files converted using cmd: dos2unix) if that makes any difference.

Thanks in advance

My most recent code:

Code: Select all


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

// #define DEBUG


// some global data
const int MAX_NUM_WORDS = 200;
int G[MAX_NUM_WORDS][MAX_NUM_WORDS];
int visited[200];

// Assume size of both strings is greater than 1
// and that they are the same size 
// and not the same string
bool isDistOneAway(const string& s1, const string& s2)
{
	if(s1 == s2) return false;
	
	int diff = 0;
	int size = min(s1.size(), s2.size());
	for(int i = 0; i < s1.size(); i++)
		if(s1[i] != s2[i])
		{
			diff++;
			if(diff > 1) return false;
		}
	if(s1.size() != s2.size() && diff != 0) return false;
	return true;
}

// start - current node in bfs process
// dest - destination
// level - which level are we on
// size - how many nodes should we concern ourselves with here
int breadthFirstSearch(int start, int dest, int size)
{
	if(start == dest) return 0;
	queue< pair<int, int> > Q;
	Q.push(make_pair(start, 0));
	
	while(!Q.empty())
	{	
		pair<int,int> r = Q.front();
		int id = r.first;
		Q.pop();
		if(id == dest) return r.second;
			
		for(int i = 0; i < size; i++)
			if(G[id][i] == 1)
				if(visited[i] == 0)
				{
					Q.push(make_pair(i, r.second+1));
				}
		visited[id] = 1;
	}
	
	return -1;
}


int main()
{
	int N;
	cin>>N;
	
	int words_used = 0;
	for(int i = 0; i < N; i++)
	{
		if(i != 0) cout<<endl;
		// reset graph, reset as minimal an amout of memory as possible
		for(int x =0; x < 200; x++)
		for(int y =0; y < 200; y++)
			G[x][y] = 0;
			
		words_used = 0;
		// a vector for each word length
		// some of these i.e. 0 and 1 are unused
		vector<int> vec[11];
		map<string, int> int_map;
		vector<string> id_map;
		
		string str;
		
		while(true)
		{
			getline(cin, str);
			if(str == "" || str == "\n")continue;
			if(str == "*") break;
			// we dont care about "" input since it will never
			// be used and hence does not affect results
			int id = id_map.size();
			id_map.push_back(str);
			
			// each string in dictionary guaranteed to be unique
			vec[str.size()].push_back(id);
			int_map[str] = id;
			words_used++;
			
			#ifdef DEBUG
				cout<<"\t\tread : \""<<str<<"\""<<endl;
			#endif
		}
		
		#ifdef DEBUG
			cout<<"the maps: "<<endl;
			for(int i = 0; i < id_map.size(); i++)
			{
				cout<<"vec : "<<id_map[i]<<endl;
				cout<<"map : "<<int_map[id_map[i]]<<endl<<endl;
			}	
			
			cout<<"\t\tabout to create the graph"<<endl;
		#endif
			
		// create the graph
		// same length words
		for(int j = 1; j < 10; j++)
		for(int x = 0; x < (int)(vec[j].size()-1); x++)
		{
			for(int y = x+1; y < (int)vec[j].size(); y++)
			{
				if(isDistOneAway(id_map[vec[j][x]],id_map[vec[j][y]]))
				{
					G[vec[j][x]][vec[j][y]] = 1;
					G[vec[j][y]][vec[j][x]] = 1;
					#ifdef DEBUG
						cout<<"\t\tadded : "<<id_map[vec[j][x]]<<" ---> "<<id_map[vec[j][y]]<<endl;
					#endif
				}
			}
		}
		// now different length words
		for(int j = 1; j < 10-1; j++)
		for(int x = 0; x < (int)(vec[j].size()); x++)
		{
			for(int y = 0; y < (int)vec[j+1].size(); y++)
			{
				string temp = " " + vec[j][x];
				if(isDistOneAway(id_map[vec[j][x]],id_map[vec[j+1][y]])
					|| isDistOneAway(temp, id_map[vec[j+1][y]]))
				{
					G[vec[j][x]][vec[j+1][y]] = 1;
					G[vec[j+1][y]][vec[j][x]] = 1;
					#ifdef DEBUG
						cout<<"\t\tadded : "<<id_map[vec[j][x]]<<" ---> "<<id_map[vec[j+1][y]]<<endl;
					#endif
				}
			}
		}
		#ifdef DEBUG
			cout<<"\t\twords used = "<<words_used<<endl;
		#endif
	
		// read the next line
		while(true)
		{
			if(cin.peek() == '\n') break;
			string word1, word2;
			cin>>word1;
			if(cin.eof()) break;
			cin>>word2;;
		
			#ifdef DEBUG
				cout<<"\t\ttest : "<<word1<<"  and  "<<word2<<endl;
			#endif
			
			if(word1 == word2)
				cout<<word1<<" "<<word2<<" "<<0<<endl;
			else
			{
				// RUN BREADTH FIRST SEARCH
				for(int j = 0; j < 200; j++)
					visited[j] = 0;
				
				
				if(word1.size() != 1 || word2.size() != 1)
				{
					int steps = breadthFirstSearch(int_map[word1], int_map[word2], words_used);
					cout<<word1<<" "<<word2<<" "<<steps<<endl;
				}
				else
					cout<<word1<<" "<<word2<<" "<<1<<endl;	
			}
			if(cin.peek()=='\n')
				cin.ignore(1);
		}
		if(cin.peek()=='\n')
			cin.ignore(1);
	}
	return 0;
}


Re: 429 Word Transformation

Posted: Sun May 23, 2010 9:51 pm
by sazzadcsedu
gt1404 wrote:
"a" can be changed to "ba" and "ab" legally.
No,it can't be.Because the problem statement clearly states that
Each successive word differs from the previous word in only a single character position while the word length remains the same.
So word must be same length to transform.

Re: 429 Word Transformation

Posted: Wed Aug 25, 2010 9:59 pm
by gt1404
ahhh I should be more careful. Thanks for the tip.

-gt