## 10701 - Pre, in and post

Moderator: Board moderators

tymoszenko
New poster
Posts: 3
Joined: Tue Dec 30, 2003 6:24 pm
Location: Brazil
Contact:

### 10701 - Pre, in and post

Hello!

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
There is a another same problem in volume 5 (536 tree recovery). Search for it.
"Everything should be made simple, but not always simpler"

wiktor
New poster
Posts: 5
Joined: Wed Sep 22, 2004 6:13 pm

### Re: 10701 WA- Help me with some critical I/O

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

hectorUCI
New poster
Posts: 4
Joined: Tue Mar 01, 2005 8:36 am

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
j:=1;
While (j<=C) and (j<=2000) do
begin
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.

hectorUCI
New poster
Posts: 4
Joined: Tue Mar 01, 2005 8:36 am

### Problem 10701 It works but ... WA

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
j:=1;
While (j<=C) and (j<=2000) do
begin
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.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
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...

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Respuesta en el foro del volumen...

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
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.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
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.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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...

Ami ekhono shopno dekhi...
HomePage

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### 10701 Runtime Error

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

Code: Select all

#include <stdio.h>

char pre[53], in[53];

int n, i;

void post(int p, int root, int q)
{
int left, right;
for (left=0; left<n; left++) if (pre[left] == in[root]) break;
left++;
for (i=0; i<n; i++) if (in[i] == pre[left]) break;
if (root > p) post(p, i, root-1);
for (right=left+1; right<n; right++)
{
for (i=0; i<n; i++) if (pre[right] == in[i]) break;
if (i > root) break;
}
if (root < q) post(root+1, i, q);
putchar(in[root]);
}

void main()
{
int t;

scanf("%d", &t);
while (t--)
{
scanf("%d%s%s", &n, pre, in);
for (i=0; i<n; i++) if (pre[0] == in[i]) break;
post(0, i, n-1);
putchar('\n');
}
}
Narek Saribekyan

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### 10701

Try taking an array of larger size which gave me WA.
Last edited by linux on Thu Sep 11, 2008 9:26 pm, edited 1 time in total.
Solving for fun..

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am