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

Post Reply
User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra » Sun Apr 27, 2003 4:08 pm

thanks,I've already try that way before but with misstyping.
i use '\' instead of '/' . :wink:

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.

Post by Diskerr » Fri May 09, 2003 4:34 pm

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

Post by Hisoka » Fri May 09, 2003 5:23 pm

Thanks for correction, for this problem, judge should not gave you a wrong input. this is my mistake.

bye....... :oops:

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

Oh, sorry

Post by Diskerr » Fri May 09, 2003 5:41 pm

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

Post by Hisoka » Fri May 09, 2003 8:39 pm

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.... :D

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

112 WA :(

Post by Runtime_Error » Sun May 11, 2003 10:51 pm

i got WA after my program running about 1 second!!!
is there any trick in this problem?? :cry: :(

[cpp]
#include <iostream.h>
#include <stack>
#include <stdlib.h>

using std::stack;

void main()
{
int br, W, SN;
char a, integer[15];
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

Post by Ronaldo » Fri May 23, 2003 2:11 pm

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

Post by ngchumin » Tue Jul 01, 2003 6:25 pm

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:

Post by visoft » Thu Jul 03, 2003 3:31 pm

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?

Post by Mistr » Thu Jul 03, 2003 8:48 pm

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.

Post by kisow » Fri Jul 11, 2003 9:03 am

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

Post by kisow » Tue Jul 15, 2003 3:18 am

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

Post by Ruslan Shevelyov » Thu Aug 14, 2003 7:17 am

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

Post by de » Thu Aug 28, 2003 12:57 pm

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)

Post by xbeanx » Thu Aug 28, 2003 4:10 pm

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".

Post Reply

Return to “Volume 1 (100-199)”