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.
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.
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:
-xenon
Did you consider:
Happy huntingIn the case of multiple paths of least value you should pick the one with the least value on the terminal node.
-xenon
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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]
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]
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]
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.
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.
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:](./images/smilies/icon_evil.gif)
[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.
-
- 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?
Thanks in advance.
RS
![:lol:](./images/smilies/icon_lol.gif)
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);
}
RS
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
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.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]
Is there any limit for string length?
-
- 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
![:)](./images/smilies/icon_smile.gif)
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- 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* 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;
}
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- 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
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
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);
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.
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.
Here are some more...
Input:
Output:
Hope it helps.
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
Code: Select all
11
8
5
Ami ekhono shopno dekhi...
HomePage
HomePage
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.
Please check these line:
Hope it helps.
Bye~
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;
}
Bye~