10701 - Pre, in and post

[tymoszenko]

Hello!

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

[anupam]

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

[wiktor]

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

[hectorUCI]

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.

[hectorUCI]

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.

[neno_uci]

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]

Respuesta en el foro del volumen...

[sumankar]

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]

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]

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]

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.

[snar]

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');
	}
}

[linux]

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

[emotional blind]

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.