10150 - Doublets

[Lampiao]

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

Thanks!

[Lampiao]

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

[lowai]

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

[Adrian Kuegel]

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

[lowai]

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]

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]

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]

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]

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]

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]

i dont think if two different length strings are doublets. my AC code gives both "No solution." for your test data.
gut lak!

[junbin]

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]

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]

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]

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.