Page **1** of **5**

### 10029 - Edit Step Ladders

Posted: **Fri May 24, 2002 9:41 am**

by **Adrian Kuegel**

What does it mean:

"x can be transformed to y by adding, deleting, or changing one letter".

Is it an exclusive or or do I have to take into account transformations from dog to go?

Is there any other trick in this problem?

I always get Wrong Answer and don't know why.

Posted: **Thu Jun 06, 2002 4:35 pm**

by **gvcormac**

Do you get the correct output for the sample? Did you read the question really carefully?

You are barking up the wrong tree looking for a weird interpretation of "edit step." "change a letter"

means "replace a letter by any other letter."

Posted: **Thu Jun 06, 2002 5:22 pm**

by **Adrian Kuegel**

Thank you. I was asking, because I had tried to find a mistake in my program very long, and I wanted to be sure that I understood the problem right. Now I found the mistake (it was in the removing part).

Posted: **Fri Jun 21, 2002 1:27 pm**

by **Revenger**

Can anybody say why this program gets Runtime Error (Invalid Memory Reference)

[pascal]Program p10029;

Const MaxN = 25000;

Var Voc : Array[1..MaxN]of Record

W : String;

l,max : Integer;

End;

i,N : Integer;

Function FindWord(Var S : String) : Integer;

Var l,r,m : Integer;

begin

l:=1;

r:=N;

While r-l>1 Do Begin

m:=(l+r) div 2;

if Voc[m].W>S then r:=m else l:=m;

End;

if m>1 then if Voc[m-1].W=S then begin FindWord:=m-1; Exit; end;

if Voc[m].W=S then begin FindWord:=m; Exit; end;

if m<N then if Voc[m+1].W=S then begin FindWord:=m+1; Exit; end;

FindWord:=-1;

end;

Procedure SolveFor;

Var S,Snew : String;

i,j : Integer;

Ch : Char;

begin

S:=Voc[N+1].W;

(* try to change *)

for i:=1 to length(S) do

for Ch:='a' to 'z' do begin

Snew:=S;

Snew*:=Ch;*

j:=FindWord(Snew);

if j<>-1 then

if Voc[j].l+1>Voc[N+1].l then

Voc[N+1].l:=Voc[j].l+1;

end;

(* try to delete *)

for i:=1 to length(S) do begin

Snew:=S;

Delete(Snew,i,1);

if Snew='' then Break;

j:=FindWord(Snew);

if j<>-1 then

if Voc[j].l+1>Voc[N+1].l then

Voc[N+1].l:=Voc[j].l+1;

end;

(* try to add *)

for i:=1 to length(S)+1 do

for Ch:='a' to 'z' do begin

if i>1 then Snew:=Copy(S,1,i-1) else Snew:='';

Snew:=Snew+Ch;

if i<=length(S) then Snew:=Snew+Copy(S,i,length(S)-i+1);

j:=FindWord(Snew);

if j<>-1 then

if Voc[j].l+1>Voc[N+1].l then

Voc[N+1].l:=Voc[j].l+1;

end;

end;

begin

N:=0;

While Not Eof(InPut) Do begin

Readln(Voc[N+1].W);

Voc[N+1].l:=1;

if N+1>1 then Voc[N+1].max:=Voc[N].max else Voc[N+1].max:=1;

SolveFor;

if Voc[N+1].l>Voc[N+1].max then Voc[N+1].max:=Voc[N+1].l;

N:=N+1;

end;

Writeln(Voc[N].max);

end.[/pascal]

### 10029 - Edit Step Ladders

Posted: **Tue Oct 29, 2002 1:17 am**

by **jpfarias**

What is a good approach to solve this problem?

I've thought of two, but each got TLE...

At the first one, I had done the LIS algorithm, checking everytime if a word is a edit step of another.

In the second attemp I generate all the possible edit steps for each word read and did a binary search on the list.

So, can anyone help me with this problem?

Thanx in advance!

Jo

Posted: **Tue Oct 29, 2002 1:30 pm**

by **junjieliang**

I haven't solved this problem yet but... what is the complexity of your LIS? I know there's a O(n log n) method, but I never really tried implementing it.

IF I get AC on this problem I'll get back to you

Posted: **Tue Oct 29, 2002 6:29 pm**

by **jingye**

both methods should run in time.

check your implementations.

Posted: **Wed Oct 30, 2002 12:12 am**

by **jpfarias**

Did you get AC on this problem?

Or do u know the time limit is now 10 seconds?

So, if these methods I've described can run under 10 secs, then I will redo my implementation, may be I've missed something...

Thanx in advance!

Jo

Posted: **Thu Oct 31, 2002 3:20 am**

by **jingye**

Yes, I have two different programs that get AC under the time limit.

Posted: **Thu Oct 31, 2002 4:56 am**

by **junjieliang**

Just wondering, what's the complexity of your LIS program? I figured my O(n log n) implementation wouldn't work in this problem (it makes use of the fact that if i > j and j > k then i > k, which doesn't hold here)...

Thanks.

Posted: **Thu Oct 31, 2002 9:09 am**

by **Dominik Michniewski**

How can I obtain a time-complexity of LIS O(nlogn) ??

I think, that it is an algorithm, which have O(n^2) time-complexity ...

Regards

Dominik

Posted: **Fri Nov 01, 2002 4:51 am**

by **jingye**

my LIS program is O(n^2).

Posted: **Mon Nov 04, 2002 5:11 am**

by **jpfarias**

Hi, can u send me your code, so I can see what's wrong with my solution?

Or may I send u my code and u see what's wrong for me?

Any help will be good for me!

Thanks!

Jo

Posted: **Mon Nov 04, 2002 7:01 am**

by **junjieliang**

I thought about this problem, and still have no idea how you got a O(n^2) running in time. How do you check if a word is an edit step ladder of another? Mine runs a loop through the string... Is yours any faster?

Still thinking...

Posted: **Mon Nov 04, 2002 8:12 am**

by **jingye**

Sorry, I misunderstood you. No, my program is the same as yours. It should run in time.