Page 2 of 5
Posted: Sun Nov 10, 2002 2:57 pm
I have two method to solve your problem, and both of them are related to the size of the strings (but I think the O(t*n) is better than O(n^2) where t refers to the length of the string)

In these two methods, you must find the step ladders exactly from its string (not finding them with checking) for example when you have the word "Step" you can understand that it is adjacent to "Stop".

In the first method , you can take all the words, Sort them with O(n logn) and then for each word find its adjacents by binary search. this method is O(t*n*logn). But the second is O(t*n).

The second method uses hash instead of Sorting and Searching with binary search. (Ofcourse I ignore problems that may happen by hashing). in this method you can make your graph with the above idea but not having the sort and search cost. but also having the hash cost.

### 10029

Posted: Tue Jul 22, 2003 7:34 pm
input:
cat
dig
dog
fig
fin
fine
fog
log
wine

output:
5

why it is 5?
maybe i am misunderstanding the question.
the task is that we need to find out the smallest step for transforming each pairs of word from the top one by one..(cat->dig),(dig ->dog), (dog->fig),.....
and among these smallest number, we figure out the largest one?

Posted: Sat Aug 02, 2003 7:58 am
The task is to find the "longest" step ladder, which is a sequence of words that each words can be "transformed from" the previous word in the sequence.

For the sample input, the longest step ladder is
"dig fig fin fine wine". Which consists of four changing transformations and one adding transformation.

Posted: Fri Aug 29, 2003 6:59 am
Thanks!
fully understand!

Posted: Thu Sep 04, 2003 6:59 pm
Can anyone tell me how to solve this problem efficiently?

Posted: Thu Sep 04, 2003 7:10 pm

### 10029 - plz help, i can't find what is wrong with my program

Posted: Mon Sep 22, 2003 5:43 pm
This is my code :

Code: Select all

``````//++++++++++++++++++++++++++++++++++++++++
//  10029 - Edit Step Ladders
//  (red)
//  [url]http://acm.uva.es/p/v100/10029.html [/url]
//++++++++++++++++++++++++++++++++++++++++

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
//===========================================
#define MAX_N 25011
#define MAX_ST 20

int n;
int le[MAX_N];
char s[MAX_N][MAX_ST];

int result;

int c[MAX_N];

//===========================================
void input()
{
int i;
n=0;
while (scanf("%s",s[++n])==1);

--n;

for (i=1;i<=n;++i)
le[i]=strlen(s[i]);
}
//============================================
void sort(int first, int last)
{
int i,j,z;
char g[MAX_ST];
char u[MAX_ST];

i=first; j= last;
strcpy(g,s[(i+j)/2]);

do{
while (strcmp(s[i],g)==-1) ++i;
while (strcmp(s[j],g)== 1) --j;

if (i<=j)
{
strcpy(u,s[i]);
strcpy(s[i],s[j]);
strcpy(s[j],u);
z=le[i]; le[i]=le[j]; le[j]=z;
++i;
--j;
}
} while (i<=j);

if (i<last)  sort(i,last);
if (j>first) sort(first,j);
}
//===========================================
// search u in the array s[1..x]
int search(int x, char u[])
{
int first,last,g;
int cmp;

first=1; last=x;
while (first<=last)
{
g=(first+last)/2 ;

cmp=strcmp(u,s[g]);

if (cmp==0)
return c[g];
else
if (cmp==1)
first=g+1;
else
last=g-1;
}

return -1;
}
//============================================
void calculate(int x)
{
int i,j,max,search_result;
char u[MAX_ST];

max=1;

// deleting
for (i=0;i<le[x];++i)
{
for (j=0;j<i;++j)
u[j]=s[x][j];
for (j=i+1;j<=le[x];++j)
u[j-1]=s[x][j];

search_result=search(x-1,u);

if (max<search_result+1) max=search_result+1;
}

// replacing
for (i=0;i<le[x];++i)
{
strcpy(u,s[x]);

for (j='a';j<='z';++j)
if (j!=s[x][i])
{
u[i]=j;
search_result=search(x-1,u);

if (max<search_result+1) max=search_result+1;
}
}

//inserting
for (i=0;i<=le[x];++i)
{
for (j=0;j<i;++j)
u[j]=s[x][j];
for (j=i+1;j<=le[x]+1;++j)
u[j]=s[x][j-1];

for (j='a';j<='z';++j)
{
u[i]=j;
search_result=search(x-1,u);

if (max<search_result+1) max=search_result+1;
}
}

// updating
c[x]=max;
if (result<max) result=max;
}
//============================================
void solve()
{
int i;

if (n==0) { result=0;return;}
result=1;
c[1]=1;

for (i=2;i<=n;++i)
calculate(i);
}
//============================================
void output()
{
printf("%d\n",result);
}
//============================================
int main()
{
freopen("test.txt","r",stdin);
input();
//    sort(1,n);
solve();
output();
return 0;
}
``````
i did submit my program for several times. I have tested any trick i could guess. But it was always WA.

plz help me.

ken

Posted: Sat Feb 14, 2004 9:34 pm
Shahab wrote:I have two method to solve your problem, and both of them are related to the size of the strings (but I think the O(t*n) is better than O(n^2) where t refers to the length of the string)

...

The second method uses hash instead of Sorting and Searching with binary search. (Ofcourse I ignore problems that may happen by hashing). in this method you can make your graph with the above idea but not having the sort and search cost. but also having the hash cost.
I don't understand how you do it regardless to the size of alphabet! I've implemented the method with hashing, but I get TLE. Distribution in hash table is almost ideal. I set hash table size to M > N (really large table), where N is # of words in dictionary. I've noticed only words which differ at last letter have "adjacent" hash values.
So, my algorithm for constructing a graph has time complexity O(N*T*A), where T is word length, and A is size of alphabet.

How to do it without factor A?

Best Regards,
Maxim

Posted: Sat Feb 14, 2004 11:11 pm
I don't think he completely bypassed the size of the alphabet, but I think he ignored it because it could be treated as a constant.

You can pass the time limit with hashing too, if you have a good implementation. Check out little joey's comments at:
http://online-judge.uva.es/board/viewto ... f8298c32a5

Posted: Sun Feb 15, 2004 4:48 pm
Whinii F. wrote:I don't think he completely bypassed the size of the alphabet, but I think he ignored it because it could be treated as a constant.

You can pass the time limit with hashing too, if you have a good implementation. Check out little joey's comments at:
http://online-judge.uva.es/board/viewto ... f8298c32a5
Yeah, I've read that topic. I know it's a constant, but a "large" one. It does matter because 26 times slower can be crucial. Anyway, in last post I said my algorithm had time complexity O(N*T*A), and that wasn't true. It was O(N*A*T**) actually because hash function I used takes time linear in size of string to be hashed.
Problem was in data structure I used for representing the graph. I used set<int> from STL and that was killing program running time. Eventually I got AC with 4.771 secs.

Thanks to all!

Maxim

### 10029 Test Case

Posted: Thu Feb 19, 2004 1:24 pm

Code: Select all

``````ab
ba
``````

### 10029 help! TLE

Posted: Thu Jul 07, 2005 8:53 am
Hi,

I've read the other posts on 10029, and from what I've read it seems to me my implementation should work. I think the culprit may be in my calcVariations() function, where I generate all possible edit steps for a string.. maybe STL string is too slow for this? In any case, I wrote my own linked list data structure for the graph which I thought would speed things up enough to get AC, but apparently not..

Any help would be great appreciated! Thanks

Code: Select all

``````// this code written by Andrew Rothbart, 2005
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int MAXSIZE = 16; // size of largest word in dictionary

string dict[25000];
int ct;

struct node {
node* next;
int val;
};

struct root {
node *next;
int length;
};

struct custGraph {
root* words[25000];

void add(int pos, int ins) {

root* n = words[pos];
node* temp = new node;

temp->val = ins;
temp->next = n->next;
n->next = temp;

return;
}

bool contains(string str) {
return binary_search(dict, dict+ct, str);
}

};

custGraph graph;

int calcLength(int index) {
root *curr = graph.words[index];
if (curr->length) return curr->length;

node *nd = curr->next;
int max = 0, temp;

while (nd != 0) {
temp = calcLength(nd->val);
if (temp > max) max = temp;
nd = nd->next;
}

curr->length = max + 1;
return max + 1;
}

// connects graph.words[pos] to str if str is in the graph (ie. dict)
void addToGraph(int pos, string str) {

string* lb = lower_bound(dict, dict+ct, str);

if (*lb != str) return;

return;
}

void calcVariations(string str, int pos) {

string temp;

// try deleting letters
for (int i = 0; i < str.size(); i++) {
temp = str; temp.erase(i,1);
if (!temp.size() || temp < str) continue;
}

// try changing letters
for (int i = 0; i < str.size(); i++) {
for (int k = (int)str[i]+1; k <= 122; k++) {
temp = str; temp[i] = (char)k;
}
}

if (str.size() >= MAXSIZE) return;

for (int i = 0; i <= str.size(); i++) {
for (int k = 97; k <= 122; k++) {
string c;
temp = str; c += (char)k;
temp.insert(i, c.c_str());
if (temp < str) continue;
}
}

return;
}

int main() {

string str;
ct = 0;

while (cin >> str) dict[ct++] = str;

for (int i = 0; i < ct; i++) {
root* n = new root;
n->next = 0;
n->length = 0;
graph.words[i] = n;

calcVariations(dict[i], i);
}

int max = 1, temp;
for (int i = 0; i < ct; i++) {
temp = calcLength(i);
if (temp > max) max = temp;
}

cout << max << endl;

return 0;
}

``````

### editing step with Hash?

Posted: Thu Aug 11, 2005 2:09 pm
May anyone explain the "hash" method you use?

How do you check if two hash is an editing step?

or do you generate all possible editing steps? (i think this would be very large&slow)

### TLE

Posted: Thu Aug 11, 2005 6:17 pm
I get a TLE using any algorithm I have on mind, anyone can give me some hints?
I suspect my string ops are too slow, but i have no ide how to improve it.

### AC

Posted: Fri Aug 12, 2005 7:29 pm
my program get AC after change from STL map to hash_map.

STL map in gcc use rb_tree, which is slow in inserting.