536 - Tree Recovery

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

Moderator: Board moderators

limelight_team
New poster
Posts: 3
Joined: Sat Dec 29, 2001 2:00 am

536 - Tree Recovery

Post by limelight_team »

could anybody give me a hint on what algorithm might be used on this problem?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra »

Hi!

This is quite an easy task.

You have to do this using recurence.

in the input the first letter is the root.
If you find this letter in the inord reprezentation you will know the length of the left and right subtree. And now you can do the same with left subtree... ( the second letter in preord is its root)..

And using the recurence you can do it with all tree...

I hope it will help :smile:

limelight_team
New poster
Posts: 3
Joined: Sat Dec 29, 2001 2:00 am

Post by limelight_team »

Thanks a lot, cyfra, I got p.536 AC'd.

ffkre
New poster
Posts: 3
Joined: Tue Feb 11, 2003 4:13 pm

536 get WA. any test case,help~~~~~~~

Post by ffkre »

i got WA, any test case???

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

What's your method?

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric »

[pascal]Deleted as I get accepted[/pascal]

I am not familiar with the binary tree.
Can anyone tell me why I get WA?
I only know that the 1st letter in the pre-order is the root and the total number of path is N-1.
Can anyone give me some sample input/output?

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric »

Finally I get accepted.
My array is a little bit (just a '[') too small and cause my counting sort fail.

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Location: Bangladesh
Contact:

Post by Grinder »

Hi, Can any one help why RUNTIME ERROR:

This is my code:

Code: Select all

#include <stdio.h>
#include <string.h>

#define MAX 100

int findRoot(char in[],char item)
{
	int i;
	for(i = 0; i < strlen(in); i++)
		if(in[i] == item)
			return i;
	return 0;
}

void postfix(char pre[],int pre_low,char in[],int in_low,int in_up)
{
	int root;
	if(in_low > in_up) return;
	if(in_low == in_up)
	{
		printf("%c",in[in_low]);
		return;
	}
	root = findRoot(in,pre[pre_low]);
	if(root > in_low) postfix(pre,pre_low+1,in,in_low,root-1);
	if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
	printf("%c",in[root]);

}	
	
void main()
{
	char prefix[MAX];
	char infix[MAX];

	while(scanf("%s %s",prefix,infix) == 2)
	{
		postfix(prefix,0,infix,0,strlen(infix)-1);
		printf("\n");
	}
}
Plz help me. :(
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Location: Bangladesh
Contact:

Post by Grinder »

Hi, Can any one help why RUNTIME ERROR:

This is my code:

Code: Select all

#include <stdio.h>
#include <string.h>

#define MAX 100

int findRoot(char in[],char item)
{
	int i;
	for(i = 0; i < strlen(in); i++)
		if(in[i] == item)
			return i;
	return 0;
}

void postfix(char pre[],int pre_low,char in[],int in_low,int in_up)
{
	int root;
	if(in_low > in_up) return;
	if(in_low == in_up)
	{
		printf("%c",in[in_low]);
		return;
	}
	root = findRoot(in,pre[pre_low]);
	if(root > in_low) postfix(pre,pre_low+1,in,in_low,root-1);
	if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
	printf("%c",in[root]);

}	
	
void main()
{
	char prefix[MAX];
	char infix[MAX];

	while(scanf("%s %s",prefix,infix) == 2)
	{
		postfix(prefix,0,infix,0,strlen(infix)-1);
		printf("\n");
	}
}
Plz help me. :(
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

RTEEEEE

Post by I LIKE GN »

hello...
i can't figure out of RTE...
would u please help???????

Code: Select all

ACed...// removed
thanks.
Last edited by I LIKE GN on Thu Jan 19, 2006 1:08 pm, edited 1 time in total.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN »

please help meeeeeee!!!!!!!!!!
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN »

:-?
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv »

Grinder, your code's

Code: Select all

   if(root < in_up) postfix(pre,root+1,in,root+1,in_up); 
is wrong.

If anyone is basing your algorithm on his, try the following test case:

Code: Select all

ABCEDFGH ECBDFAHG

Johan
New poster
Posts: 7
Joined: Wed Dec 21, 2005 5:27 pm

536 wa

Post by Johan »

Hi,

My 536 passes the example testcase, but a submission results in a wrong answer. Does anybody have a hint or perhaps some nice testcases?

The idea behind the code below is this:

1) The root is first element of the pre-order traversal
2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
3) The children of the current root are the first elements of the sub-pre-order-traversals.
4) recurse and put the numbers of the children in an array
5) recurse in post-order traversal through the new tree

Kind regards,

Johan

Code: Select all

#include <string> 
#include <vector> 
#include <cstdlib> 
using namespace std; 
 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<string> vs; 
typedef vector<vs> vvs;
#define pb push_back 
#define sz(v) ((int)(v).size()) 


vs splitvs(string s,string split)
{
  vs uit; string nu;
  split+=char(0); s+=char(0);
  for(int i=0;i<sz(s);i++)
  {
    if(split.find(s[i])!=string::npos)
    { if(sz(nu)>0)uit.pb(nu); nu=""; }
    else nu+=s[i];
  }
  return uit;
}


void go(vi left,vi right,int current)
{
  if(left[current]!=-1) go(left,right,left[current]);
  if(right[current]!=-1) go(left,right,right[current]);
  printf("%c",current+64);
}


void fill(vi &left, vi &right, string pre, string in)
{
  char root=pre[0];
  int r=in.find(root);
  string lin=in.substr(0,r), rin=in.substr(r+1), lpre, rpre;

  for(int i=1;i<sz(pre);i++)
    if(lin.find(pre[i])!=string::npos)
      lpre+=pre[i];
    else 
      rpre+=pre[i];

  if(sz(lpre)>0)
  {
    left[root-64]=lpre[0]-64;
    fill(left,right,lpre,lin);
  }
  if(sz(rpre)>0)
  {
    right[root-64]=rpre[0]-64;
    fill(left,right,rpre,rin);
  }
}


int main()
{
  char buffer[1000];

  while(gets(buffer))
  {
    vs p=splitvs(buffer," "); 
    if(sz(p)==0)
    { printf("\n"); continue; }
    string pre=p[0],in=p[1]; 
    vi left(26,-1), right(26,-1);
    
    //build tree
    fill(left,right,pre,in);    

    //traverse tree
    go(left,right,pre[0]-64); printf("\n");
  }

  return 0;
}
[/code]

Johan
New poster
Posts: 7
Joined: Wed Dec 21, 2005 5:27 pm

Post by Johan »

Well it worked with only minor changes for a quite similar problem here in the archive, so I'll count the point. Thanks.

Post Reply

Return to “Volume 5 (500-599)”