## 112 - Tree Summing

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

Moderator: Board moderators

ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
thanks,I've already try that way before but with misstyping.
i use '\' instead of '/' . thanx.
Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

### Prob 112. Tree Summing, I got TLE.

I've searched all of the articles related to prob 102,
but there were no one who got TLE.

My idea is :
1. Build tree from string
2. Find all of the possible combinations to make I (integer)
through "INORDER" tree traverse.

but I got TLE.
It works fine in negative inputs.

I think that if we want to find integer 'I', we must search all of the tree nodes.
Right? If it is, my problem isn't at step 2.

Somebody have tricky inputs which make my code fool?

I tested with Hisoka's, but it works fine except following one :
0 (1()
(-2 () (1()())))
)
Hey, it has one more extra right parenthesis, isn't it?
I must consider such a wrong input?

This is my code:
[cpp]
// Problem 112. Tree Summing at http://acm.uva.es/p/v1/112.html

#include <cstdio>
#include <cctype>
#include <string>

using namespace std;

struct NodeType {
int Value;
NodeType* Left;
NodeType* Right;

NodeType():Value(0),Left(NULL),Right(NULL) {}
~NodeType()
{
if (Left != NULL)
delete Left;

if (Right != NULL)
delete Right;
}
};

int getNodeString(string T, string& N, int Start);
void getTreeString(string& T);
bool treeTraverse(NodeType* Root, int I);
NodeType* buildTree(string T);

int main()
{
int I;
string T;
NodeType* Root = NULL;

while (scanf("%d", &I) != EOF) {
getTreeString(T);

Root = buildTree(T);

if (Root != NULL && treeTraverse(Root, I))
printf("yes\n");
else
printf("no\n");

delete Root;
}
}

bool treeTraverse(NodeType* Root, int I)
{
if (Root == NULL)
return false;
else if (I - Root->Value == 0 && Root->Left == NULL && Root->Right == NULL)
return true;
else
return treeTraverse(Root->Left, I - Root->Value)
|| treeTraverse(Root->Right, I - Root->Value);
}

int getNodeString(string T, string& N, int Start)
{
int Parentheses = 1, End;

N = "(";
for (int i = Start + 1; i <= T.size() && Parentheses != 0; i++) {
N = N + T;
if (T == '(')
Parentheses++;
else if (T == ')') {
End = i;
Parentheses--;
}
}

return End;
}

NodeType* buildTree(string T)
{
NodeType* Root;

int Value, Parentheses = 1, Start, End;
char Dummy;
string LeftNode, RightNode;

if (T == "()") {
return NULL;
} else {
Root = new NodeType;

sscanf(T.c_str(), "%c%d", &Dummy, &Value);

Root->Value = Value;

for (int i = 1; i <= T.size(); i++) {
if (T == '(') {
Start = i;
break;
}
}

getNodeString(T, RightNode, getNodeString(T, LeftNode, Start) + 1);

Root->Left = buildTree(LeftNode);
Root->Right = buildTree(RightNode);

return Root;
}
}

void getTreeString(string& T)
{
int Parentheses = 1;
char C;

while (scanf("%c", &C) != EOF) {
if (C == '(')
break;
}

T = "(";
while (Parentheses != 0) {
scanf("%c", &C);

if (C == '(') {
Parentheses++;
T = T + C;
} else if (C == ')') {
Parentheses--;
T = T + C;
} else if (isdigit(C) || C == '-') {
T = T + C;
}
}

while (C != '\n')
scanf("%c", &C);
}
[/cpp]

Thanks.[/quote]
Sorry for my poor English.
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
Thanks for correction, for this problem, judge should not gave you a wrong input. this is my mistake.

bye....... Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

### Oh, sorry

I didn't want to hurt you, Hisoka

Sorry for my rudeness
Sorry for my poor English.
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hello, I think you not understand about my previous post. I only give you my thanks, because you correction my sample I/O, and this is good. You never hurt me...

bye.... Runtime_Error
New poster
Posts: 5
Joined: Sat Oct 05, 2002 8:01 pm
Location: Yerevan, Armenia
Contact:

### 112 WA :(

i got WA after my program running about 1 second!!!
is there any trick in this problem??  [cpp]
#include <iostream.h>
#include <stack>
#include <stdlib.h>

using std::stack;

void main()
{
int br, W, SN;
char a, integer;
stack<int> weight;
stack<int> subnum;
int sum, I, q, i;
bool yes, frbr;

while (cin >> I) {
br = 0;
frbr = true;
q = 0;
sum = 0;
yes = false;
while (1) {
cin >> a;
if (a == '(') {
if (q == 0)
q = 1;
if (q == 2)
q = 3;
br++;
if (!frbr) {
SN = subnum.top();
subnum.pop();
SN++;
subnum.push(SN);
}
if (frbr)
frbr = false;
}
if (a == ')') {
br--;
if (br == 0)
break;
if (q == 1)
q = 2;
if (q == 3) {
if (sum == I)
yes = true;
q = 0;
}
W = weight.top();
SN = subnum.top();
weight.pop();
subnum.pop();
if (SN == 1) {
weight.push(W);
subnum.push(SN);
}
else
sum = sum - W;
}
if ((a >= '0' && a <= '9') || a == '-' || a == '+') {
q = 0;
i = 0;
while ((a >= '0' && a <= '9') || a == '-' || a == '+') {
integer = a;
i++;
cin >> a;
}
integer = '\0';
cin.putback(a);
W = atoi(integer);
SN = 0;
weight.push(W);
subnum.push(SN);
sum = sum + W;
}
}
if (yes)
cout << "yes\n";
else
cout << "no\n";
cin.clear();
}
}
[/cpp]
A Runtime Error Has Occured, Do You Wish To Debug?
Ronaldo
New poster
Posts: 5
Joined: Fri May 23, 2003 1:45 pm

### Da qo hamar plav utel chi

Et Xndir@ Exela mer Olimpiadayi xndir@ ev mi txa lucela.Gna iranic harcru.
ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am

### 112

hi....
does anybody has any idea wat the judge input is like?
i keep getting time limit exceeded even though i dun use any recursion!

thanks!
visoft
New poster
Posts: 1
Joined: Thu Jul 03, 2003 3:18 pm
Contact:
I've got the WA! Constantly...
I try with 0, i try with negative values..
It worked. (on my computer) But there...

The algorithm works for all test cases i can think about.

Do you know, a leading ora trailing space matters? Shouldn't i got an PE warning?

Anybody?
Mistr
New poster
Posts: 1
Joined: Thu Jul 03, 2003 8:43 pm

### did u try these tests?

i took these tests from Hisoka, they helped me. maybe it will help u 2.

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()())
) ) )
() ) () )
yes

0 ( )
no

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()()))))
(6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()())))
yes

0 (1()
(-2 () (1()())))
yes

1 (1 () (0 ()()) )
yes

good luck
kisow
New poster
Posts: 3
Joined: Fri Jul 11, 2003 8:46 am
Contact:

### help me...I've got WA, too.....give me some test case.

I've a trouble with it.

I can't find bug in my code.
It works well for any test case that I thought.

help me, please...
[cpp]
#include <cctype>
#include <iostream>
using namespace std;

#define STACK_MAX 10000

main()
{
char cByte;
bool bResult;
int i, iTmp;
int iLeaf, iStack, iValue;
int iaStack[STACK_MAX];

cin >> iValue;
while(cin)
{
bResult = false;
iLeaf = 0, iStack = 1;
while(cin && (cByte = cin.get()) != '(');
while(cin && iStack > 0 && (cByte = cin.peek()))
{
if(cByte == '(')
{
cin.ignore();
while(cin && isspace(cin.peek())) cin.ignore();
if(cin.peek() == ')') iLeaf++, cin.ignore();
else iStack++;
}
else if(cByte == ')')
{
cin.ignore();
iStack--;
}
else if(isdigit(cByte) || cByte == '-')
{
cin >> iaStack[iStack - 1];
iLeaf = 0;
}
else cin.ignore();

if(!bResult && iLeaf == 2)
{
iLeaf = iTmp = 0;
for(i = 0; i < iStack; i++)
iTmp += iaStack;
if(iTmp == iValue) bResult = true;
}
}
cout << (bResult ? "yes" : "no") << endl;
cin >> iValue;
}

return 0;
}
[/cpp]
kisow
New poster
Posts: 3
Joined: Fri Jul 11, 2003 8:46 am
Contact:

### 112 - help me. plz

why.. WA...?

give me some test case or hint...plz.

I'm very tired....help me

[cpp]
#include <cctype>
#include <iostream>
using namespace std;

#define STACK_MAX 10000

main()
{
char cByte;
bool bResult;
int i, iTmp;
int iLeaf, iStack, iValue;
int iaStack[STACK_MAX];

cin >> iValue;
while(cin)
{
bResult = false;
iLeaf = 0, iStack = 1;
while(cin && (cByte = cin.get()) != '(');
while(cin && iStack > 0 && (cByte = cin.peek()))
{
if(cByte == '(')
{
cin.ignore();
while(cin && isspace(cin.peek())) cin.ignore();
if(cin.peek() == ')') iLeaf++, cin.ignore();
else iStack++;
}
else if(cByte == ')')
{
cin.ignore();
iStack--;
}
else if(isdigit(cByte) || cByte == '-')
{
cin >> iaStack[iStack - 1];
iLeaf = 0;
}
else cin.ignore();

if(!bResult && iLeaf == 2)
{
iLeaf = iTmp = 0;
for(i = 0; i < iStack; i++)
iTmp += iaStack;
if(iTmp == iValue) bResult = true;
}
}
cout << (bResult ? "yes" : "no") << endl;
cin >> iValue;
}

return 0;
}
[/cpp]
Ruslan Shevelyov
New poster
Posts: 15
Joined: Fri Aug 08, 2003 8:13 pm
Location: Russia, Moscow
Contact:

### Re: 112 - help me. plz

I tested your program with random data; some tests for which your program produced wrong results are:
autotester wrote:8(8(2(1()())())())
8(8(3(7()())())())
4(4(2(4()())())())
5(5(4()(1(7(3()())(4()()))(4(3()())())))())
21(7()(5()(5()(4(1(7()())())()))))
47(7(9()(1(4()(7()(5(9(3(4(10()())())())(5(9(5(6(3(1(9()(2(3()(9(1(3(7()())(9()()))(9(5()(2()()))()))(7()())))(5(2()(6()(2()())))())))())(7()(2()(3()()))))(9()(10(4()(3()(4(3()(5()()))())))())))(3()()))())()))(6(10()())()))))()))())
24(9()(6()(1(2(9(8(7()())(1(1(7()())())(8()())))())(6(5(9()())())()))())))
15(8()(3(7(4(4()(9(6(3(3()())(9(3(3(8()())(7()()))())()))(3()()))()))())())(3(1(8(5(4(2()(4()(3(1()(10()(9()())))())))())(2()()))())())())))
18(4(9()())(1()(4()(9(3(9()(7()(8(6()())(5()(5()())))))(8(4()(1()()))()))()))))
www.Find-a-Drug.org distributed computing project
de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

### 112 WA

I don't know what's wrong in my code><

I've considered the negative inputs and 0 () is "no"

[cpp]
#include <iostream.h>
#include <stdio.h>

int find;
int n;
int ans;
int ansc;

void DFS(int sum)
{
int s=0;
int temp=0;
char c;
int us=1;

while (scanf ("%c",&c)==1)
{
if (c=='-')
{
us=-1;
continue;
}

if (c==' ' || c=='\n')
continue;
else if (c>='0' && c<='9')
temp=temp*10+c-'0';
else
{
if (c==')')
{
if (temp==0)
{
if (ansc==0)
{
ans=sum;
ansc++;
}
else
{
if (sum==ans)
{
if (ans==n)
{
find=1;
return;
}
}
else
{
ansc=1;
ans=sum;
}
}
}
return;
}

DFS(sum+temp*us);
while (scanf ("%c",&c)==1 && c!='('){};
DFS(sum+temp*us);
}
}
}

int main()
{
char c;

//freopen ("112.txt","w",stdout);

while (scanf ("%d",&n)==1)
{
find=0;

while (scanf ("%c",&c)==1 && c!='('){};
ansc=0;
DFS(0);

if (find)
cout << "yes" << endl;
else
cout << "no" << endl;
}

return 0;
}
[/cpp]
xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)
I didn't debug your code, but maybe you should focus on this:

Code: Select all

``````INPUT:
22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3
(2 (4 () () )
(8 () () ) )
(1 (6 () () )
(4 () () ) ) )
5 ()

0 ()
-1 (-1()())
77 (77(1()())())
-77 (-77()())

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()())
) ) )
() ) () )

0 ()

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()()))))
(6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()())))

0 (1()
(-2 () (1()())))

1 (1 () (0 ()()) )

0 (0 ()())

8(8(2(1()())())())
8(8(3(7()())())())
4(4(2(4()())())())
5(5(4()(1(7(3()())(4()()))(4(3()())())))())
21(7()(5()(5()(4(1(7()())())()))))
47(7(9()(1(4()(7()(5(9(3(4(10()())())())(5(9(5(6(3(1(9()(2(3()(9(1(3(7()())(9()()))(9(5()(2()()))()))(7()())))(5(2()(6()(2()())))())))())(7()(2()(3()()))))(9()(10(4()(3()(4(3()(5()()))())))())))(3()()))())()))(6(10()())()))))()))())
24(9()(6()(1(2(9(8(7()())(1(1(7()())())(8()())))())(6(5(9()())())()))())))
15(8()(3(7(4(4()(9(6(3(3()())(9(3(3(8()())(7()()))())()))(3()()))()))())())(3(1(8(5(4(2()(4()(3(1()(10()(9()())))())))())(2()()))())())())))
18(4(9()())(1()(4()(9(3(9()(7()(8(6()())(5()(5()())))))(8(4()(1()()))()))()))))
``````

Code: Select all

``````CORRECT OUTPUT:
yes
no
yes
no
no
yes
no
yes
yes
no
yes
yes
yes
yes
no
no
no
no
no
no
no
no
no

YOUR OUTPUT:
yes
no
yes
``````
Perhaps you are not reading blank lines correctly?

Also --

Code: Select all

``````INPUT:
38

(5
(6
(4
()()
)
(3
()()
)
)
(7
(2
(1
()()
)
(10
()
(9
(5
()()
)
(2
()()
)
)
)
)
()
)
)

Output should be "yes" yours gives "no".
``````