429 - Word Transformation

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

Moderator: Board moderators

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Fri Sep 02, 2005 1:41 pm

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...??

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

429 - TLE

Post by Donotalo » Thu Sep 21, 2006 10:42 am

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!
Image

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi » Sat Mar 17, 2007 8:09 am

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..
Last edited by kolpobilashi on Sat Mar 17, 2007 3:21 pm, edited 1 time in total.
Sanjana

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Mar 17, 2007 12:55 pm

Replace the 'main' function...

Code: Select all

Removed...
Minor changes, so no big deal. Hope it helps.
Last edited by Jan on Sat Mar 17, 2007 3:36 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi » Sat Mar 17, 2007 3:22 pm

That's it !!! :o :o
thanx Jan... :)
Sanjana

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Thu Jun 21, 2007 4:25 pm

I use binary search and 2D array to implement...
Y WA...?

Code: Select all

AC-ed
I read the question wrong again.. :( 
Last edited by kn on Fri Jun 22, 2007 1:50 pm, edited 1 time in total.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Thu Jun 21, 2007 7:07 pm

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??

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Thu Jun 21, 2007 7:55 pm

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
Last edited by kn on Fri Jun 22, 2007 1:49 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jun 21, 2007 9:58 pm

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.
Ami ekhono shopno dekhi...
HomePage

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Fri Jun 22, 2007 12:37 pm

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

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Sat Oct 20, 2007 11:58 am

Hi i am trying with BFS,but WR
Is there any tricky case?

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 429 - Word Transformation

Post by deadangelx » Sat Nov 01, 2008 9:12 am

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

gt1404
New poster
Posts: 6
Joined: Sat Dec 26, 2009 10:16 am

429 - Word Transformation

Post by gt1404 » Sat Dec 26, 2009 10:31 am

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;
}


sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 429 Word Transformation

Post by sazzadcsedu » Sun May 23, 2010 9:51 pm

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.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

gt1404
New poster
Posts: 6
Joined: Sat Dec 26, 2009 10:16 am

Re: 429 Word Transformation

Post by gt1404 » Wed Aug 25, 2010 9:59 pm

ahhh I should be more careful. Thanks for the tip.

-gt

Post Reply

Return to “Volume 4 (400-499)”