10150 - Doublets

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

Moderator: Board moderators

Lampiao
New poster
Posts: 3
Joined: Thu Nov 22, 2001 2:00 am
Location: Recife, Brazil
Contact:

Post by Lampiao » Thu Nov 22, 2001 9:05 pm

Words of diferent sizes are considered doublets? For example, the words "booster" and "boosters" are doublets?

Thanks!
Gustavo Santos

Lampiao
New poster
Posts: 3
Joined: Thu Nov 22, 2001 2:00 am
Location: Recife, Brazil
Contact:

Post by Lampiao » Tue Nov 27, 2001 3:13 pm

The answer is NO. Words of diferent length aren't doublets! I found out it after getting WA :smile:

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

10150

Post by lowai » Sun Nov 03, 2002 6:53 am

I used heuristic search and got TLE, and I used Indexing Tree to store and find the words as well.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Nov 03, 2002 2:36 pm

You can use binary search each time you are searching for a word, and to find the shortest sequence use bfs.

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Sun Nov 03, 2002 2:54 pm

Right. I use hueristic BFS. I think it is fast enough. and indexing tree can also perform the word-searching in a quick way.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Nov 03, 2002 3:21 pm

If you make the bfs in a proper way, it is fast enough. My program runs 2.4 seconds.
Did you mark the words that you already reached? And how do you determine what words can be reached in next step? I tried to change the letter at each position of the word and if I found the changed word in the dictionary and I haven't reached it before, I pushed the index of the word in the queue.

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Mon Nov 04, 2002 2:14 am

I did it in the same way.
The time complexity of looking up a word in the indexing tree is proportional to the length of the word. For the length is not greater the 16,
i think it is faster than binary search.

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

10150 - Keep timing out, can't seem to optimize...

Post by PJYelton » Tue Jul 29, 2003 8:30 pm

I'm trying to solve prob 10150 - Doublets - and it keeps timing out no matter how much I optimize it. I've done what it seems like others have done and who have gotten time less than 3 secs, but mine always comes back saying limit exceeded. I'm pretty new to C++ and I'm wondering if maybe somewhere I get into an infinite loop with the judges input that doesn't happen with anything I've tried. Anyways, here is the code that uses a BFS and from what I can tell I can't find any way to optimize it further. It replaces every letter in the word at the top of the queue and uses binary search to see if that new word is in the dictionary, and if it exists and hasn't been checked yet it adds to the queue.
[cpp]
/* @JUDGE_ID: 32250TW 10150 C++ "Simple Iteration" */
/* @BEGIN_OF_SOURCE_CODE */
#include <iostream>
#include <vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int min(int x, int y) {if (x<y) return x; else return y;}
vector<string> dict;

struct point
{
point() : run(-1) {};
int run; // run number, used to keep track if this point has been searched already
int name;
int dist;
point* pred;
vector<int> conn; // vector of points it is connected to
};

void split(string &s1, string &s2, string &s3)
{
int x;
for (x=0; x<s1.length(); x++)
{
if (s1[x]==' ')
break;
}
s2=s1.substr(0,x);
if (x>=s1.length())
s3="";
else
s3=s1.substr(x+1,s1.length()-x-1);
}

int binarySearch (vector<string> &vec, string &s)
{
int bott, top, mid ;
bott = 0 ; top = vec.size() -1 ;
int L = ( top + bott ) / 2 ;
bool found;

if (vec[L] == s)
found = true ;
else
found = false ;

while (bott <=top && !found)
{
mid = top + bott / 2 ;
if ( vec [mid] == s )
{
found = true;
L = mid ;
}
else if (vec [mid] < s )
bott = mid + 1 ;
else
top = mid-1 ;
}

if (found)
return L;
else
return -1;
}


void recurse(point *p)
{
if (p->pred!=NULL)
recurse(p->pred);

cout<<dict[p->name]<<endl;
}

int main()
{
int run=0;
bool first=true;
vector<point*> vec;

int x,y,z;
while (1)
{
string s;
getline(cin,s);
if (s=="")
break;
dict.push_back(s);
}

sort(dict.begin(), dict.end());

for (x=0; x<dict.size(); x++)
{
point *p;
p=new point;
p->name=x;
p->pred=NULL;
vec.push_back(p);
}

while (1)
{
run++;
string s,s1,s2;
if (!first)
{
cout<<endl;
}
else
first=!first;

getline(cin,s);

split(s,s1,s2);

int first=binarySearch(dict,s1);
int end=binarySearch(dict,s2);

if (first==-1 || end==-1)
{
cout<<"No solution."<<endl;
continue;
}

if (s1==s2)
{
cout<<s1<<endl;
continue;
}

queue<point*> q;

vec[first]->pred=NULL;
vec[first]->run=run;
vec[end]->pred=NULL;

q.push(vec[first]);

while (!q.empty())
{
bool done=false;
for (y=0; y<dict[q.front()->name].length(); y++)
{
string s1=dict[q.front()->name];
for (char c='a'; c<='z'; c++)
{
s1[y]=c;
z=binarySearch(dict,s1);
if (z!=-1)
{
vec[q.front()->name]->conn.push_back(z);
vec[z]->conn.push_back(q.front()->name);
}
}
}
for (x=0; x<vec[q.front()->name]->conn.size(); x++)
{
if (vec[vec[q.front()->name]->conn[x]]->run!=run)
{
vec[vec[q.front()->name]->conn[x]]->dist=q.front()->dist+1;
vec[vec[q.front()->name]->conn[x]]->pred=q.front();
vec[vec[q.front()->name]->conn[x]]->run=run;

q.push(vec[vec[q.front()->name]->conn[x]]);
if (dict[vec[q.front()->name]->conn[x]]==s2)
{
done=true;
break;
}

}
}

if (done)
break;

q.pop();
}

if (vec[end]->pred==NULL)
cout<<"No solution."<<endl;
else
recurse(vec[end]);

}

return 0;

}
/* @END_OF_SOURCE_CODE */
[/cpp]

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

Clarification...

Post by rbuchan » Fri Oct 17, 2003 8:16 pm

I am wondering about the doublets. Do they have to be the same length? Or, can something like

coastal
costal
postal

be a legitimate path? What is the purpose of keeping track of the node being visited or not? My method uses a <set> for the dictionary, and <queue> to keep track of the paths for each of the different letters in the word. I just keep a min_path and then print out the queue, unless it has not been found, and then "No solution.".

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

10150: Doublets... WA?

Post by junbin » Wed Jan 28, 2004 7:00 am

Just to confirm:

1) Can two different length strings be considered doublets? eg: "a" and "ab" or "a" and "abc" ?

2) Do the starting and ending strings have to be in the dictionary?

If anyone has an AC program, can they please run the following test data through their code? The results will answer my questions. Thank you in advance!


Test data:

Code: Select all

abc
ab
ac
bac

abc bac
dbc bac

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Jan 28, 2004 8:23 am

i dont think if two different length strings are doublets. my AC code gives both "No solution." for your test data.
gut lak! :)
Kalo mau kaya, buat apa sekolah?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Wed Jan 28, 2004 2:35 pm

titid_gede wrote:i dont think if two different length strings are doublets. my AC code gives both "No solution." for your test data.
gut lak! :)
I'm still getting WA.. and my code takes like 8seconds to complete the calculations.. :p

Last few questions:

1) If the starting or ending words are not in the dictionary, will there be a solution?

2) Can there be a solution of zero length (ie: the starting word maps in 1 move to the ending word)

3) What happens if both the starting and ending words are the same?


Anyone with an AC code, please run the following test data through it and post the results.. thanks in advance!


Test data:

Code: Select all

aba
abc
acc
acd

aba bcd
zba acc
zba bcd
aba abc
aba aba

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Wed Jan 28, 2004 2:50 pm

Ok.. I managed to get AC. So for the sake for those who are having trouble with this question, I'll answer my own questions:

1) If the starting or ending words are not in the dictionary, will there be a solution?

No solution


2) Can there be a solution of zero length (ie: the starting word maps in 1 move to the ending word)


Yes.

3) What happens if both the starting and ending words are the same?

You need another word to go in between the two words. eg:

aba
aba

is NOT allowed. You need:

aba
abc
aba


Anyway, for the test data, the output is:

No solution.

No solution.

No solution.

aba
abc

aba
abc
aba

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

Post by fpmc » Wed Jul 21, 2004 2:38 am

Hi,

I doubt your solution to the case when the first string = second string. I sent a code that yields for the test case

Code: Select all

abc

abc abc
an answer

Code: Select all

abc
So I guess this case doesn't exist.

Also, does anybody know how to do this in C++? I tried to use sets/maps which supposingly uses binary search but it was way too slow. I did the same with C's bsearch and it worked in 2.4 secs.
I search for documentation and I found a binary_search function in C++ that returns bool, but does not give index, which is quite useless. Anybody know of a better method (not using index tree) in C++ please please let me know ^_^

Frank

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Wed Jul 21, 2004 11:10 am

fpmc wrote:Hi,

I doubt your solution to the case when the first string = second string. I sent a code that yields for the test case

Code: Select all

abc

abc abc
an answer

Code: Select all

abc
So I guess this case doesn't exist.

Also, does anybody know how to do this in C++? I tried to use sets/maps which supposingly uses binary search but it was way too slow. I did the same with C's bsearch and it worked in 2.4 secs.
I search for documentation and I found a binary_search function in C++ that returns bool, but does not give index, which is quite useless. Anybody know of a better method (not using index tree) in C++ please please let me know ^_^

Frank


In general, a hand-coded b-search will be faster than the provided STL one. Also, I try to avoid STL as a whole since the library is not very efficient as a whole.

Post Reply

Return to “Volume 101 (10100-10199)”