10029  Edit Step Ladders
Moderator: Board moderators
10029
I'm stuck on 10029, getting WA, and wonder if anyone can provide assistance.
I've checked my "fast" solution (that I submit) against the "naive" slow solution, and my answers match up, so I don't know what I'm doing wrong ... unless I've misunderstood the question.
An edit step that "adds" or "deletes" a letter can do so anywhere in the word, correct?
Are the following valid edit steps: dg > dog, abcd > bcd, abcd > acd?
Moreover, the step ladder is supposed to be in lexicographic order. Since we are given the input in lexicographic order, I assume the longest step ladder is just a subsequence of the input, no?
What would be the longest edit step ladder in
abc
abd
bbc
I'm assuming 2, since the ladder has to be in lexicographic order. The ladder is abc>abd or abc>bbc. If the lexicographic order restriction was lifted, we could do bbc>abc>abd or abd>abc>bbc.
Thanks.
I've checked my "fast" solution (that I submit) against the "naive" slow solution, and my answers match up, so I don't know what I'm doing wrong ... unless I've misunderstood the question.
An edit step that "adds" or "deletes" a letter can do so anywhere in the word, correct?
Are the following valid edit steps: dg > dog, abcd > bcd, abcd > acd?
Moreover, the step ladder is supposed to be in lexicographic order. Since we are given the input in lexicographic order, I assume the longest step ladder is just a subsequence of the input, no?
What would be the longest edit step ladder in
abc
abd
bbc
I'm assuming 2, since the ladder has to be in lexicographic order. The ladder is abc>abd or abc>bbc. If the lexicographic order restriction was lifted, we could do bbc>abc>abd or abd>abc>bbc.
Thanks.

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
Re: question about 10029 (Edit Step Ladder)
The o/p for
abc
abd
bbc
2
So, I think there is nothin wrong with your understanding of the problem. Just one thing to say...
Perhaps you would like to share your algo.
abc
abd
bbc
2
So, I think there is nothin wrong with your understanding of the problem. Just one thing to say...
I believe you have also considered the case of "change". (Though your sample I/O tells that you have .. but still just in case )gubd wrote: An edit step that "adds" or "deletes" a letter can do so anywhere in the word, correct?
Perhaps you would like to share your algo.
Where's the "Any" key?
Hi.
Yep. I considered the change of one letter to another.
My "naive" slow algorithm is similar to the standard algo for solving Longest Increasing Subsequence:
Assuming I know the longest step ladder that each word belongs to up to the i'th word, I can then find the longest step ladder on the (i+1)st word (call it w_(i+1)) by scanning the first i words looking for a word w_j (1 <= j <= i) such that w_j > w_(i+1) is an edit step, and the edit step ladder length that ends at word w_j is maximal (i.e., for any other word w_k, 1<=k<=i, such that w_k>w_(i+1) is an edit step, the length of the edit step ladder ending at w_k is <= the length of the edit step ladder ending at w_j). If there's no such word, then length of the edit step ladder that w_(i+1) belongs to is 1 (i.e. , w_(i+1) starts a new edit step ladder). I determine the longest edit step ladder length by keeping track of the value of the longest edit step ladder seen after processing each word.
This algo is O(n^2) and, since the dictionary can contain up to 25,000, is too slow.
My "fast" algorithm is similar except that I use hashing to keep track of the words: everytime I process a word w having c characters, I hash it c+1 different ways. The i'th (1<=i<=c) way of hashing it basically involves calculating the hash on the string except that I omit the i'th character from the calculation. The c+1'th way hashes the entire word without omitting any letters. For all the hashes I calculate, I search the buckets in the hash table for a word y such that y > w is an edit step, and the step ladder length ending at word y is maximal. After I found it, I add w to the table (hashed the c+1 different ways just described).
The reason (I think) this will work is best illustrated by an example:
Say the dictionary is
abcd
bcd
bce
bcf
 We hash abcd several ways: (bcd, acd, abd, abc, abcd). We won't find a word y such that y > abcd is an edit step, so the edit step length of the ladder ending with abcd is 1.
 We hash bcd several ways: (cd, bd, bc, bcd). When we look at the bucket to which 'bcd' hashed we find abcd>bcd is an edit step (and it's the maximal one), so the length of the ladder ending with bcd is 2.
 We hash bce several ways: (ce, be, bc, bce). In this case the hash on 'bc' takes us to the bucket containing bcd and we'll find that bcd>bce is an edit step (and it's the maximal one) , so the length of the ladder ending with bce is the length of the ladder ending in 'bcd' + 1 == 3.
 We hash bcf as (cf, bf, bc, bcf). The hash on 'bc' will take us to the bucket containing both 'bce' and 'bcd'. Since the length of the ladder ending on 'bce' is longer, we'll conclude that the length of the ladder ending in 'bcf' is 4.
Thanks for any comments you may have.
Yep. I considered the change of one letter to another.
My "naive" slow algorithm is similar to the standard algo for solving Longest Increasing Subsequence:
Assuming I know the longest step ladder that each word belongs to up to the i'th word, I can then find the longest step ladder on the (i+1)st word (call it w_(i+1)) by scanning the first i words looking for a word w_j (1 <= j <= i) such that w_j > w_(i+1) is an edit step, and the edit step ladder length that ends at word w_j is maximal (i.e., for any other word w_k, 1<=k<=i, such that w_k>w_(i+1) is an edit step, the length of the edit step ladder ending at w_k is <= the length of the edit step ladder ending at w_j). If there's no such word, then length of the edit step ladder that w_(i+1) belongs to is 1 (i.e. , w_(i+1) starts a new edit step ladder). I determine the longest edit step ladder length by keeping track of the value of the longest edit step ladder seen after processing each word.
This algo is O(n^2) and, since the dictionary can contain up to 25,000, is too slow.
My "fast" algorithm is similar except that I use hashing to keep track of the words: everytime I process a word w having c characters, I hash it c+1 different ways. The i'th (1<=i<=c) way of hashing it basically involves calculating the hash on the string except that I omit the i'th character from the calculation. The c+1'th way hashes the entire word without omitting any letters. For all the hashes I calculate, I search the buckets in the hash table for a word y such that y > w is an edit step, and the step ladder length ending at word y is maximal. After I found it, I add w to the table (hashed the c+1 different ways just described).
The reason (I think) this will work is best illustrated by an example:
Say the dictionary is
abcd
bcd
bce
bcf
 We hash abcd several ways: (bcd, acd, abd, abc, abcd). We won't find a word y such that y > abcd is an edit step, so the edit step length of the ladder ending with abcd is 1.
 We hash bcd several ways: (cd, bd, bc, bcd). When we look at the bucket to which 'bcd' hashed we find abcd>bcd is an edit step (and it's the maximal one), so the length of the ladder ending with bcd is 2.
 We hash bce several ways: (ce, be, bc, bce). In this case the hash on 'bc' takes us to the bucket containing bcd and we'll find that bcd>bce is an edit step (and it's the maximal one) , so the length of the ladder ending with bce is the length of the ladder ending in 'bcd' + 1 == 3.
 We hash bcf as (cf, bf, bc, bcf). The hash on 'bc' will take us to the bucket containing both 'bce' and 'bcd'. Since the length of the ladder ending on 'bce' is longer, we'll conclude that the length of the ladder ending in 'bcf' is 4.
Thanks for any comments you may have.
Yep, I was getting 1.
I just figured out what my problem was. I was doing something really silly with my collision resolution in the hashtable (overwriting some pointers by accident). This wasn't causing any of my handcrafted testcases to fail, unfortunately, so the problem only showed up when I submitted. D'oh!
After fixing I got AC in 2.7 sec with the hashing algo described above.
I just figured out what my problem was. I was doing something really silly with my collision resolution in the hashtable (overwriting some pointers by accident). This wasn't causing any of my handcrafted testcases to fail, unfortunately, so the problem only showed up when I submitted. D'oh!
After fixing I got AC in 2.7 sec with the hashing algo described above.

 New poster
 Posts: 4
 Joined: Thu Nov 09, 2006 9:08 am
10029
Hello.
I am new here. I have been getting Runtime error (SIGSEGV 11) for problem 10029... http://acm.uva.es/p/v100/10029.html
Although my program runs fine on my solaris box and algorithm seems to simple. Here is my code.
TIA
anuj
I am new here. I have been getting Runtime error (SIGSEGV 11) for problem 10029... http://acm.uva.es/p/v100/10029.html
Although my program runs fine on my solaris box and algorithm seems to simple. Here is my code.
Code: Select all
code removed
anuj
Last edited by anuj.bhargava on Fri Nov 10, 2006 1:53 pm, edited 1 time in total.

 New poster
 Posts: 4
 Joined: Thu Nov 09, 2006 9:08 am
any help would be deeply appreciated.
I just hate getting stuck.
Try giving it an input file with 25000 words.
This part of your program would try to allocate 596Mb on the stack in that case:
On UVa, default memory limit is just 32 Mb (and you have even less than that for the stack.)
Also, forum description says "if there is a thread about your problem, please use it. If not, create one with its number in the subject."
Please don't ignore it the next time.
This part of your program would try to allocate 596Mb on the stack in that case:
Code: Select all
int s=v.size();
bool arr[s][s];
Also, forum description says "if there is a thread about your problem, please use it. If not, create one with its number in the subject."
Please don't ignore it the next time.

 New poster
 Posts: 4
 Joined: Thu Nov 09, 2006 9:08 am
If you tried to allocate 596Mb normally (as a static array, or dynamically  new/malloc), you would get MLE.
But you try to allocate so much memory on the stack.
http://www.google.com/search?q=sigsegv+stack+overflow
But you try to allocate so much memory on the stack.
http://www.google.com/search?q=sigsegv+stack+overflow
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I don't think you need to bother about those super fast times. Since this problem only needs to print one number (single case), it takes only a limited amount of submissions to find out what that number actually is if you have an accepted solution. Then submit a program that only prints this number and you get accepted in 0 seconds.rio wrote:I sovled this problem with 0.207 sec.
In the rank list, there are some people solved it with 0.00 sec.
I don't have any clue with such fast algorithm.
Could someone give me a hint?
Thanks in advance.

Sory for my poor English.
I haven't tried, but I think 0 seconds isn't even enough to read the input, so all those on the top of the list are probably cheating little w@nk3rs.
And 0.207 is a very good time!

 New poster
 Posts: 4
 Joined: Thu Nov 09, 2006 9:08 am
Plz help me
when I use an array of vectors... thereby not allocating huge ammount of memory, I get a TLE. I dont understand it. array lookup is O(1) and each vector should not be verry large. Please somebody help me in this regard. what data structure I should use. what is the basic flaw here?
Code: Select all
 The program I'll compile begins here: 
#include <string>
#include <vector>
#include <math.h>
#include <iostream.h>
#include <algorithm>
bool is_edit_step(string s1,string s2){
int count=0;
if(abs(s1.size()s2.size())>1)
return false;
else if(s1.size()==s2.size()){
for(int i=0;i<s1.size();i++)
if(s1[i]!=s2[i])
count++;
if(count!=1)
return false;
else return true;
count=0;}
else if(s1.size()>s2.size()){
for(int i=0;i<s2.size();i++)
if(s1[i+count]!=s2[i] && count<2){
count++;
i;}
if(count>1) return false;
else return true;
count=0;}
else return is_edit_step(s2,s1);}
int m(int a,int b){
if(a>b) return a;
else return b;}
void main(){
vector<string> v;
string str;
while(cin>>str)
v.push_back(str);
int s=v.size();
vector<int> arr[s];
for(int i=0;i<s;i++)
arr[i].push_back(i);
vector<int>::iterator iter;
for(int i=0;i<s;i++)
for(int j=i+1;j<s;j++)
if(is_edit_step(v[i],v[j]))
arr[i].push_back(j);
int a[s];
a[s1]=1;
for(int i=s2;i>1;i)
{ int max=0;
for(int j=i+1;j<s;j++){
iter=find(arr[i].begin(),arr[i].end(),j);
if(iter != arr[i].end())
max=m(max,1+a[j]);}
a[i]=max;}
int max=0;
for(int i=0;i<s;i++)
if(a[i]>max)
max=a[i];
cout<<max<<endl;}