10701 - Pre, in and post

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10701 - Pre, in and post

Post by tymoszenko »

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:

Post by anupam »

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

Post by wiktor »

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

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

10701 Wrong Answer WHYYYYY????

Post by 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
New poster
Posts: 4
Joined: Tue Mar 01, 2005 8:36 am

Problem 10701 It works but ... WA

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

Post by 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. :D

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

Post by neno_uci »

Respuesta en el foro del volumen...

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

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

Post by neno_uci »

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

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. :wink:

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by 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 :wink:

Suman.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

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

10701 Runtime Error

Post by 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');
	}
}
Narek Saribekyan

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

10701

Post by linux »

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
Location: Bangladesh
Contact:

Re: 10701

Post by emotional blind »

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.

Post Reply

Return to “Volume 107 (10700-10799)”