548 - Tree

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

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

548 - Tree

Post by Adrian Kuegel » Wed Jul 10, 2002 11:31 pm

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

Post by xenon » Thu Jul 11, 2002 10:12 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jul 11, 2002 9:09 pm

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

Post by DFS » Sat Jan 18, 2003 12:48 am

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

Post by eloha » Mon Jun 02, 2003 11:19 am

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

Post by eloha » Tue Jun 03, 2003 11:29 am

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. :evil:
[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

Post by Red Scorpion » Wed Jun 04, 2003 3:47 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[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 :lol: :lol:

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Thu Jun 05, 2003 12:34 pm

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:

Post by Dominik Michniewski » Thu Jun 05, 2003 2:39 pm

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

Post by ahmed hasan » Fri Feb 18, 2005 12:08 pm

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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Wed Mar 23, 2005 3:38 pm

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

Post by Pregunt » Thu Jun 16, 2005 8:23 am

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
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:

Post by Pregunt » Sat Jun 18, 2005 5:41 am

Raiyan:

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

Post by Jan » Tue May 09, 2006 2:57 am

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

Post by pineapple » Sat Feb 17, 2007 4:59 am

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~

Post Reply

Return to “Volume 5 (500-599)”