10029 - Edit Step Ladders

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

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

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

[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]

[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

[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

[jingye]

both methods should run in time.
check your implementations.

[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

[jingye]

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

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

[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

[jingye]

my LIS program is O(n^2).

[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

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

[jingye]

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