10029  Edit Step Ladders
Moderator: Board moderators
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.
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.

 New poster
 Posts: 39
 Joined: Wed Jan 22, 2003 11:02 am
10029
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?
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?

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
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.
For the sample input, the longest step ladder is
"dig fig fin fine wine". Which consists of four changing transformations and one adding transformation.
JongMan @ Yonsei

 New poster
 Posts: 39
 Joined: Wed Jan 22, 2003 11:02 am

 New poster
 Posts: 9
 Joined: Sat Jun 29, 2002 10:59 am
 Location: china
 Contact:
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
10029  plz help, i can't find what is wrong with my program
This is my code :
i did submit my program for several times. I have tested any trick i could guess. But it was always WA.
plz help me.
thanks in advance
ken
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=g1;
}
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[j1]=s[x][j];
search_result=search(x1,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(x1,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][j1];
for (j='a';j<='z';++j)
{
u[i]=j;
search_result=search(x1,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;
}
plz help me.
thanks in advance
ken
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.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.
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

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
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://onlinejudge.uva.es/board/viewto ... f8298c32a5
You can pass the time limit with hashing too, if you have a good implementation. Check out little joey's comments at:
http://onlinejudge.uva.es/board/viewto ... f8298c32a5
JongMan @ Yonsei
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.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://onlinejudge.uva.es/board/viewto ... f8298c32a5
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
Code: Select all
ab
ba
10029 help! TLE
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
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;
graph.add(pos, lb  dict);
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;
addToGraph(pos, temp);
}
// 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;
addToGraph(pos, temp);
}
}
// try adding letters
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;
addToGraph(pos, temp);
}
}
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?
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)
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
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.
I suspect my string ops are too slow, but i have no ide how to improve it.
Code: Select all
AC
my program get AC after change from STL map to hash_map.
STL map in gcc use rb_tree, which is slow in inserting.
STL map in gcc use rb_tree, which is slow in inserting.