OJ Board

Hello!

I solved this problem (10701), but I am stell getting WA. I know that this problem is easy, but I can

There is a another same problem in volume 5 (536 tree recovery). Search for it.

Maybe this will help:
1
8 ABCHDEFG HCBDAFEG
Output: HCDBFGEA

Here you are my PASCAL code for 10701 problem. What I do is to build the tree and then traverse it in PostOrder. I think it works but... WA... Does anybody could help me, please???

Sincerelly yours Hector

Program ACM10701;
Type
BTree = ^Node;
Node = record
value : Char;
L,R : BTree;
end;
Traversal = String[54];

Var
Preorder,Inorder,Postorder : Traversal;
A : BTree;
C,N,i,j,k:integer;
V:Char;

Procedure MakeTree(var P:BTree;POrder:Traversal);
var
Pos1,Pos2 : Traversal;
Begin
If (POrder<>'') Then
Begin
V:=Preorder[1];
New(P);
P^.value := V;
P^.L:=Nil; P^.R:=Nil;
Delete(Preorder,1,1);
i:=pos(V,POrder);
if i<>0 then
begin
Pos1:=copy(POrder,1,i-1);
Pos2:=copy(POrder,i+1,length(Porder)-i+1);
MakeTree(P^.L,Pos1);
MakeTree(P^.R,Pos2);
end
else
P:=Nil;
End
End;

Procedure RecPostOrder(P:Btree);
Begin
If P<>Nil Then
begin
RecPostOrder(P^.L);
RecPostOrder(P^.R);
Write(P^.value);
end;
End;

Begin
Readln(C);
j:=1;
While (j<=C) and (j<=2000) do
begin
readln(N,Preorder);
Delete(Preorder,1,1);
for i:=1 to length(Preorder) do
begin
if not (UpCase(Preorder) in ['A'..'Z',' ']) then
delete(Preorder,i,1);
end;
k:=pos(' ',Preorder);
Postorder:=copy(Preorder,k+1,length(Preorder)-k+1);
for i:=1 to length(Postorder) do
begin
if not (UpCase(Postorder) in ['A'..'Z',' ']) then
delete(Postorder,i,1);
end;
Delete(Preorder,k,length(Preorder)-k+1);
MakeTree(A,Postorder);
RecPostOrder(A);
Dispose(A);
writeln;
j:=j+1;
end;
End.

Please somebody check it. I know it works but i received WA

Program ACM10701;
Type
BTree = ^Node;
Node = record
value : Char;
L,R : BTree;
end;
Traversal = String[54];

Var
Preorder,Inorder,Postorder : Traversal;
A : BTree;
C,N,i,j,k:integer;
V:Char;

Procedure MakeTree(var P:BTree;POrder:Traversal);
var
Pos1,Pos2 : Traversal;
Begin
If (POrder<>'') Then
Begin
V:=Preorder[1];
New(P);
P^.value := V;
P^.L:=Nil; P^.R:=Nil;
Delete(Preorder,1,1);
i:=pos(V,POrder);
if i<>0 then
begin
Pos1:=copy(POrder,1,i-1);
Pos2:=copy(POrder,i+1,length(Porder)-i+1);
MakeTree(P^.L,Pos1);
MakeTree(P^.R,Pos2);
end
else
P:=Nil;
End
End;

Procedure RecPostOrder(P:Btree);
Begin
If P<>Nil Then
begin
RecPostOrder(P^.L);
RecPostOrder(P^.R);
Write(P^.value);
end;
End;

Begin
Readln(C);
j:=1;
While (j<=C) and (j<=2000) do
begin
readln(N,Preorder);
Delete(Preorder,1,1);
for i:=1 to length(Preorder) do
begin
if not (UpCase(Preorder[i]) in ['A'..'Z',' ']) then
delete(Preorder,i,1);
end;
k:=pos(' ',Preorder);
Postorder:=copy(Preorder,k+1,length(Preorder)-k+1);
for i:=1 to length(Postorder) do
begin
if not (UpCase(Postorder[i]) in ['A'..'Z',' ']) then
delete(Postorder,i,1);
end;
Delete(Preorder,k,length(Preorder)-k+1);
MakeTree(A,Postorder);
RecPostOrder(A);
Dispose(A);
writeln;
j:=j+1;
end;
End.

El algoritmo esta bien, lo ke no esta bien es el tamanno de la cadena ke lees, piensa en el caso critico, un arbol de 52 nodos, la entrada seria:

52 (52 caracteres del recorrido en preorden) (52 caracteres del recorrido en entreorden)

lo cual da como resultado una cadena de 52+1+52+1+52=158 caracteres y tratas de leerla con una de 52.

Solo cambia el tamanno de la cadena aki:

Traversal = String[54];

por:

Traversal = String;

y esta resuelto el problema, un abrazo,

Yandry.

Btw en el volumen 5 hay un problema identico a este, se llama Tree Recovering o algo asi...

Respuesta en el foro del volumen...

neno_uci
Can we speak a more or less common language?I understood more or less,
still ... even if you guys go to the same school(as the suffix suggested, or maybe I am plain wrong.)

Regards,
Suman.

Yes, indeed we go to the same school, but i am a student and he's not.

Do you need some explanation about the problem?, his mistake was that he was using a 52 characters string to read one of at most 158..., reply me if you have doubts about it,

Yandry.

Nah! I solved that quite a while back.Anyway thanks for taking the trouble.

Actually that was on a more philanthropic note.Not to be taken otherwise

Suman.

I solved 536 and got Accepted. But for this problem I m getting WA .

My code produces right output for

1
8 ABCHDEFG HCBDAFEG

Can anyone give me some difficult or critical cases...

Thanks in advance.

Hi, please give me some test data, I'm getting RE.
Here's my code.

Try taking an array of larger size which gave me WA.

linux wrote:I think Judge's input file has some invalid input. N is greater than 52. Try some greater value of N means increase the array size. I faced the similar case I took array of 500 and got accepted.

I don't think so, I got accepted with array size 53.