10029  Edit Step Ladders
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
10029  Edit Step Ladders
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.
"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.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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 rl>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[m1].W=S then begin FindWord:=m1; 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,i1) 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]
[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 rl>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[m1].W=S then begin FindWord:=m1; 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,i1) 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
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
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

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore