## 548 - Tree

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 548 - Tree

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
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You were right. It was a bug in my code, now I got Accepted.

DFS
New poster
Posts: 1
Joined: Sat Jan 18, 2003 12:45 am

### 548 - Tree: WA

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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
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]
Last edited by eloha on Tue Jun 03, 2003 11:31 am, edited 1 time in total.

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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;
int inord, post, n, min, des;

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

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;

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);
}
``````
RS  eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
eloha wrote: 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

ahmed hasan
New poster
Posts: 9
Joined: Fri Jan 21, 2005 5:09 pm

### 548 getting TLE

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* 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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
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
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:

### 548 Tree WA

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);
until (eoln);
cant:=j;
for j:=1 to cant do
cont:=1;
arma(1,cant,1);
min:=maxlongint;
quien:=maxlongint;
pre(1,0);
writeln(quien);
until eof;
end.

Pregunt
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:
Raiyan:

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

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

### To:Red Scorpion

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.
``````if (sum <= min)