548 - Tree

[Adrian Kuegel]

Does the input contain only correct tree description or do I have to check that? And did I understand it right that the value of a path is the sum of the values of the nodes (including root and leave), for example 26 for the second input?
My algorithm works like this:
Build a tree according to the input data (that part should work, I solved a similar problem before), then dfs to find the path with minimal value. But I get WA.

[xenon]

I think you should check your code. I just got accepted using the 'simplistic' approach: recursively scan ever decreasing subsets of the input arrays, and checking path-sum and leaf-value at end-nodes. (This is building a tree + DFS, but in one pass without storing the tree). For the path-sum I took the sum of all the node-values, including root- and end-leaf.
Did you consider:

In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Happy hunting
-xenon

[Adrian Kuegel]

You were right. It was a bug in my code, now I got Accepted.

[DFS]

Howdy,

Can anybody spot the mistake in the following code?
It works on the supplied test data, but doesn't pass the
online test.

Thanks.

[cpp]
#include <iostream>
#include <sstream>
#include <vector>
#include <climits>

using namespace std;

bool populate_vector(vector<int>& v){
string s;
getline(cin, s);
istringstream sin(s);
int i;
while (sin >> i){
v.push_back(i);
}
return !v.empty();
}

int min_val;
int min_leaf;
int current_val;

int find(int val, vector<int>& v, int low, int high){
for (int i = low; i <= high; i++){
if (v == val)
return i;
}
return -1;
}

void dfs(vector<int>& I, int lowI, int highI, vector<int>& P, int lowP, int highP){
current_val += P[highP];
if (lowI == highI && current_val <= min_val && P[highP] < min_leaf){
min_val = current_val;
min_leaf = P[highP];
}
else{
int root_pos = find(P[highP], I, lowI, highI);
if (root_pos > lowI){
dfs(I, lowI, root_pos - 1, P, lowP, lowP + (root_pos - lowI - 1));
}
if (root_pos < highI){
dfs(I, root_pos + 1, highI, P, lowP + root_pos - lowI, highP - 1);
}
}
current_val -= P[highP];
}


int main(){
while (!cin.eof() && !cin.fail()){
vector<int> inorder;
if (!populate_vector(inorder))
break;
vector<int> postorder;
populate_vector(postorder);
min_val = INT_MAX;
min_leaf = INT_MAX;
current_val = 0;
dfs(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
cout << min_leaf << endl;
}
return 0;
}
[/cpp]

[eloha]

I always got Runtime Error (Invalid memory reference), but I do not know what is wrong.
I think this problem is similar to ACM 536 Tree Recovery which I got AC.
My algorithm is make the tree by the 2 given inorder and postorder traversal sequences.
And then use inorder dfs to travel the tree and find the answer.

Here is my code:
[c]

deleted......

[/c]

[eloha]

I have found what wrong with my code.
The error is the input. I am very surprised after I submit the following code. It got RunTime Error, but I did nothing but input string.
[c]#include <stdio.h>
#define StrMax 200000000
int main()
{
char s[StrMax];

while (gets(s))
{
/* do nothing */
}

}[/c]

So I use fgetc(stdin) to read char one by one, and convert them to an int array. I got AC finally.

[Red Scorpion]

Hi eloha,
I have the same problem with you, get WA.
can you check my code whats wrong with them?

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define delenter(s) if(s[strlen(s)-1] == '\n') s[strlen(s)-1] = '\x0'

typedef struct {
    int left, right;
}t_tree;

t_tree tree[10008];
int inord[10008], post[10008], n, min, des;

void parse(char *str, int *q) {
     int i, lw=0, len=strlen(str);
     char temp[50];

     for (i=0; i<len; i++) {
         if (str[i] == ' ' && lw) {
            temp[lw] = '\x0';
            q[n++] = atoi(temp);
            lw = 0;
         }
         else if (str[i] != ' ') temp[lw++] = str[i];
     }
     if (lw) {
        temp[lw] = '\x0';
        q[n++] = atoi(temp);
     }
}

int find_post(int q, int x) {
    int i;

    for (i=0; i<n; i++) {
        if (q==post[i]) break;
    }
    return(post[i-x]);
}

void reconstruct(int p, int q, int root) {
     int i;

     for (i=p; i<=q; i++) {
         if (inord[i] == root) break;
     }
     if (i-1 >= p) {
        tree[root].left = find_post(root, q-i+1);
        reconstruct(p, i-1, tree[root].left);
     }
     if (i+1 <= q) {
        tree[root].right = find_post(root, 1);
        reconstruct(i+1, q, tree[root].right);
     }
}

void traverse(int root, int sum) {
     if (tree[root].left) {
        traverse(tree[root].left, sum + tree[root].left);
     }

     if (tree[root].right) {
        traverse(tree[root].right, sum + tree[root].right);
     }

     if (!tree[root].left && !tree[root].right) {
        if (sum <= min) {
           min = sum;
           if (root < des) des = root;
        }
     }
}

void process() {
     memset(tree, 0, sizeof(tree));
     reconstruct(0, n-1, post[n-1]);
     min = des = 2147483647;
     traverse(post[n-1], post[n-1]);
     printf ("%d\n", des);
}

int main() {
    char temp[1000000];

    while (fgets(temp, 1000000, stdin)) {
          delenter(temp);
          n = 0;
          parse(temp, inord);
          fgets(temp, 1000000, stdin);
          delenter(temp);
          n = 0;
          parse(temp, post);
          process();
    }
    return(0);
}

Thanks in advance.
RS

[eloha]

It got RunTime Error, but I did nothing but input string. [c]#include <stdio.h>
#define StrMax 200000000
int main()
{
char s[StrMax];

while (gets(s))
{
/* do nothing */
}

}[/c]

I don't know why it get Runtime Error if I set the max length of string to 200000000. But when I set the max length of string to 1000000, it works.
Is there any limit for string length?

[Dominik Michniewski]

I think that 200 MB for string is too much hehehe .... We have only 32 MB of memory at judge server, so I'm surprised, that you don't get Memory Limit Exceeded error ... This is one more reason, that I think, that memory manager works a bit strange on Linux ...

Best regards
DM

[ahmed hasan]

Code: Select all

#include<cstdio>
#include<cstring>
#include<string>
#define max 400000
#define Inf 999999999

struct TreeNode
{
	int key;
	struct TreeNode *left;
	struct TreeNode *right;
};


char s[max*5];
int InOrderPos[max];
int PostOrder[max];
TreeNode Tree;
int MinCost;
int MinLeaf;


TreeNode* Initialize(TreeNode *head)
{head->left=head->right=NULL;	return head;}


TreeNode* Makenode(int item)
{
	TreeNode *newnode=Initialize((TreeNode*)malloc(sizeof(TreeNode)));
	newnode->key=item;
	return newnode;
}

TreeNode* Insert(TreeNode* nodeptr, int newnode, int cost)
{
	if(nodeptr==NULL)
	{
		nodeptr=Makenode(newnode);
		if( (MinCost>cost+newnode) || (MinCost==cost+newnode && MinLeaf>newnode)) 
		{MinCost=cost+newnode;MinLeaf=newnode;}
		return nodeptr;
	}
	if(nodeptr->key==MinLeaf)MinCost=Inf;
	if(InOrderPos[newnode]<InOrderPos[nodeptr->key]) 
		nodeptr->left =  Insert(nodeptr->left ,newnode,cost+nodeptr->key);
	if(InOrderPos[newnode]>InOrderPos[nodeptr->key]) 
		nodeptr->right = Insert(nodeptr->right,newnode,cost+nodeptr->key);
	return nodeptr;
}


int main()
{
	int strpos;
	int sl;
	int nodenum;
	int node;
	
	freopen("ip.txt","r",stdin);
	while(gets(s))
	{
		nodenum=0;
		sl=strlen(s);
		strpos=0;
		
		while(strpos<sl &&!isdigit(s[strpos]))strpos++;
		while(strpos<sl){
			sscanf(s+strpos,"%d",&node);
			nodenum++;
			InOrderPos[node]=nodenum;
			while(strpos<sl && isdigit(s[strpos]))strpos++;
			while(strpos<sl &&!isdigit(s[strpos]))strpos++;
		}
		
		for(int c1=1;c1<=nodenum;c1++) scanf("%d",&PostOrder[c1]);
		getchar();

		Initialize(&Tree);
		Tree.key=PostOrder[nodenum];
		MinCost=Inf;
		MinLeaf=Tree.key;
		for(int c2=nodenum-1;c2>0;c2--) Insert(&Tree,PostOrder[c2],0);
		printf("%d\n",MinLeaf);
	}
	return 0;
}

[Raiyan Kamal]

Can you please explain the procedure you are using ? it is hard to understand from your code.

There can be 10000 nodes in a binary tree, so you have to take time saving measures to get rid of TLE.

You can also try these test cases :

INPUT :

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22
7 2 8 10 6 1 11 15 3 4
7 8 6 10 2 15 11 4 3 1
7 5 6 4 8 2 9 1 3 11 10 12
7 6 5 8 4 9 2 11 12 10 3 1
4 2 6 5 7 1 9 3 13 12 8 11
4 6 7 5 2 9 13 12 11 8 3 1


OUTPUT:

1
3
255
1
4
9
4

[Pregunt]

Can anybody send some test cases or tell me what is wrong in my program?

This is my code:

const
lim=10005;
type
arbol=record
i,d:integer;
q:longint;
end;
var
arb:array[0..lim] of arbol;
ino, post:array[0..lim] of longint;
j,cont,cant:integer;
min,quien:longint;

procedure arma(ini,fin,n:longint);
var
ind:integer;
begin
arb[cont].q:=post[cant-cont+1];
ind:=ini-1;
repeat
inc(ind);
until (ino[ind]=post[cant-cont+1]) or (ind=fin);
if ino[ind]=post[cant-cont+1] then
begin
if ind<fin then
begin
inc(cont);
arb[n].d:=cont;
arma(ind+1,fin,cont);
end;
if ind>ini then
begin
inc(cont);
arb[n].i:=cont;
arma(ini,ind-1,cont);
end;
end;
end;

procedure pre(i:longint;s:longint);
begin
if arb.q<>0 then
begin
inc(s,arb.q);
if (arb.i<>0) or (arb.d<>0) then
begin
pre(arb.i,s);
pre(arb.d,s);
end
else
if (s<min) or ((s=min) AND (arb.q<quien)) then
begin
min:=s;
quien:=arb.q;
end;
end;
end;
begin
repeat
fillchar(arb,sizeof(arb),0);
fillchar(post,sizeof(post),0);
fillchar(ino,sizeof(ino),0);
j:=0;
repeat
inc(j);
read(ino[j]);
until (eoln);
cant:=j;
for j:=1 to cant do
read(post[j]);
cont:=1;
arma(1,cant,1);
min:=maxlongint;
quien:=maxlongint;
pre(1,0);
writeln(quien);
until eof;
end.

[Pregunt]

Raiyan:

[Jan]

Here are some more...

Input:

Code: Select all

4 11 2 1 3 9 6
11 4 2 9 6 3 1
4 11 2 1 3 8 6
11 4 2 8 6 3 1
5 7 1
5 7 1

Output:

Code: Select all

11
8
5

Hope it helps.

[pineapple]

Red Scorpion,
First,you can use strtok() and atoi() to parse the string,it is more convenient than your parse();
Second,I think you maybe misunderstand the meaning of the last sentence:
In the case of multiple paths of least value you should pick the one with the least value on the terminal node.
Please check these line:

Code: Select all

if (sum <= min) 
{ 
      min = sum; 
      if (root < des) des = root; 
}

Hope it helps.
Bye~