10029 - Edit Step Ladders

[gubd]

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.

[Solaris]

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...

An edit step that "adds" or "deletes" a letter can do so anywhere in the word, correct?

I believe you have also considered the case of "change". (Though your sample I/O tells that you have .. but still just in case )

Perhaps you would like to share your algo.

[gubd]

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.

[Solaris]

abcd
abcd

The op is 1

What does your code show ??

[gubd]

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.

[anuj.bhargava]

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.

Code: Select all

code removed

TIA
anuj

[anuj.bhargava]

I just hate getting stuck.

[mf]

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:

Code: Select all

int s=v.size();
bool arr[s][s]; 

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.

[anuj.bhargava]

but why is it giving Runtime error (SIGSEGV 11) instead of Memory Limit Exceeded??

[mf]

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

[rio]

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.

[little joey]

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 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.

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!

[rio]

Thanks joey (and congratulation for you top!). You are right. I didn't consider the time for reading input.
----
Sory for my poor English.

[anuj.bhargava]

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[s-1]=1;
for(int i=s-2;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;}

[rio]

Your algorithm takes O(n^2). n is up to 25000 so it's too slow.

Don't try to look all pair if it's edit step or not.
A simple strategy to avoid this is clasifying the word with it's length.

And I don't recommend STL for these kind of "TLE" problems.