## 112 - Tree Summing

Moderator: Board moderators

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
hey guys,

This problem is driving me crazy :S.
First I got it WA several times. Then I changed the way I read input from reading with cin.getline to reading a character by a character for cases where 2 test share a line.
Then I got TLE for that. I changed my code to sum the tree nodes while parsing the tree not after constructing the whole tree & also got TLE :S.

I don't know what's wrong. I can't calculate the path sum in less time than this !!
Is it something about termination condition !! But the problem statement asks me to read till end of file.

Could u plz help me
---
Asmaa Magdi

Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

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

I tried to solve this problem with array representation and with linked list in the same process, but with linked list it gives me AC with 0.5 secs whereas with array it gives me TLE. Can anybody tell me why it happens?

Is it because of using an array of size 10^7?
Last edited by Samiul on Sat Jul 12, 2008 10:29 pm, edited 2 times in total.

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

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

Samiul wrote:I tried to solve this problem with array representation and with node in the same process, but with node it gives me AC with 0.5 secs whereas with array it gives me TLE. Can anybody why it happens?

Is it because of using an array of size 10^7?
you don't need this array

this problem can be solved in O(n) while reading the input with a recursive function

1989gaurav
New poster
Posts: 3
Joined: Sun Nov 09, 2008 11:15 am

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

I got wrong answer in this question, but it is working for negative test cases and some other cases. I am not getting in what condition it is failing so please help me. If someone have extra test cases for this problem please give so i can crosscheck my results.

sarker306
New poster
Posts: 2
Joined: Sat Sep 05, 2009 3:50 am

### 112

I have tested the code against almost all test cases i have found in the forum, but I cant find any find any problem here. Maybe your insights will help me with it.

Code: Select all

``````#include<stdio.h>

int I, level, Sum_level;
char flag;

void tree_sum(int x){
int n=0, val, sign=1, child=0;
char ch;

level++;
while(ch=getchar()){
if(ch==')'){
if(n==0 && x==I){
flag=2;
Sum_level++;
}
return;
}
if(ch=='-') sign=-1;
else if(ch=='('){
/*printf("%d %d\n", x , n*sign); */
tree_sum(x+sign*n);
child++;
}
else if(ch>='0' && ch<='9') n=10*n+ch-'0';

if(Sum_level && Sum_level<2 && child==2) flag=0, Sum_level=0;
}
}

int main(){
char ch;

/* freopen("data.txt", "w", stdout);*/
while(scanf("%d", &I)!=EOF){
flag=0;
level=0;
Sum_level=0;
while((ch=getchar())!='(');
tree_sum(0);
if(flag==2 && level>1) printf("yes\n");
else printf("no\n");
}

return 0;
}
``````
I should explain what I do here. I is the number I should check for. flag is indicating whether I have found a root-to-leaf path. Sum_level is just being increased when I find a path which ends in '()' . To be the path reallly a ROOT TO LEAF path, we must encounter another '()'. When we dont find it, 'Sum_level' remains '1'. then from the statement

Code: Select all

``````if(Sum_level && Sum_level<2 && child==2) flag=0, Sum_level=0;
``````
'Sum_level' and 'flag' are reset.
The variable level is just for checking whether we are encountering an empty tree. When we are getting a '(' we can increase it.... in an empty tree like this

Code: Select all

`````` ( )
``````
should not the value in level be 1?
That's all I can think of.
Any kind of help will be appreciated.
Thanks.

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 112. please, give me the test cases,..

Try this Input :

Code: Select all

``````5 (18  (-
13  ( )( ) )( )   )
0 (  1
()(-  2 ( ) ( 1 ()() ) )
)
0 (                         )
``````
Output should be :

Code: Select all

``````yes
yes
no
``````

jsimister
New poster
Posts: 1
Joined: Tue Feb 19, 2013 10:52 pm

### 112 WA

Would you please provide me with a test case for which this does not work or any suggestions? Thanks in advance.

Code: Select all

``````// problem 112
// Jonathon Simister

#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <iostream>
#include <cstdlib>

using namespace std;

class node {
public:
node(int x) {
i = x;
}

void print() {
int c;

if(i != 0) {
cout<<"("<<i;

for(c = 0;c < children.size();c++) {
children[c]->print();
}

cout<<")";
} else {
cout<<"()";
}
}

int i;
vector<node*> children;
};

int maxd(node* v) {
int max;
int c;
int ret = 1;

if(v->children.size() == 0) { return ret; }

max = 0;

for(c = 0;c < v->children.size();c++) {
if(maxd(v->children[c]) > max) {
max = maxd(v->children[c]);
}
}

ret += max;

return ret;
}

bool possible(node* v,int sum,int d,int maxd) {
int x;
int c;

if(v->children.size() == 0) {
if(sum == v->i && d == maxd) {
return true;
} else {
return false;
}
} else {
x = sum - v->i;

for(c = 0;c < v->children.size();c++) {
if(possible(v->children[c],x,d+1,maxd)) { return true; }
}

return false;
}
}

node* parsetree(const char* s,int* read) {
const char* c;
int n  = 0;
node* ret;
int cr;
node *cn;
bool neg;

if(s[0] != '(') { *read = 0; return NULL; }

c = s+1;

neg = false;

if(*c == '-') {
neg = true;
c++;
}

while(isdigit(*c)) {
n *= 10;
n += (*c)-'0';
c++;
}

if(neg) { n = 0-n; }

ret = new node(n);

while(*c == '(') {
cn = parsetree(c,&cr);

if(cn != NULL) {
ret->children.push_back(cn);
}

c += cr;
}

c++;

// assert(*c == ')');

return ret;
}

int main() {
char line[100000];
char* tree;
char* tp;
char* lp;
int sum;
int opens, closes;
int linelen;
node* root;
int x;

tree = (char*)malloc(1000000);

while(gets(line)) {
memset(tree,0,1000000);
opens = 0;
closes = 0;

tp = tree;

sscanf(line,"%d ",&sum);

lp = line;

while(isdigit(*lp) || (*lp == '-')) { lp++; }

while(true) {
while(*lp != 0) {
if(isdigit(*lp)) {
*tp = *lp;
tp++;
} else if(*lp == '-') {
*tp = '-';
*tp++;
} else if(*lp == '(') {
*tp = '(';
tp++;
opens++;
} else if(*lp == ')') {
*tp = ')';
tp++;
closes++;
}

lp++;
}

if(opens > closes) {
gets(line);
lp = line;
} else {
break;
}
}

root = parsetree(tree,&x);

/*printf(tree);
printf("\n");

root->print();
printf("\n");*/

if(possible(root,sum,1,maxd(root)) && root->children.size() > 0) { printf("yes\n"); } else { printf("no\n"); }
}

return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 112 WA

Input:

Code: Select all

``````22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
27 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
26 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
18 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))``````
Output should be:

Code: Select all

``````yes
yes
yes
yes``````
Check input and AC output for thousands of problems on uDebug!

dallen
New poster
Posts: 7
Joined: Mon Apr 22, 2013 1:06 am
Location: Asunción, Paraguay

### #112 Tree Summing WA

I'm new to programming contests and I was trying to solve problem #112. On my dev machine I pass the test cases provided in the problem and also some others I found browsing the forum, so I believe my program is correct. The problem I'm facing is making it fast enough to be accepted, I'm going to paste my code here hoping to see if anyone can give some pointers to a newbie, thanks in advance!

Code: Select all

``````import java.util.AbstractMap.SimpleEntry;
import java.util.Scanner;
import java.util.Stack;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();

while (sc.hasNextLine()) {
sb.append(sc.nextLine());
}

String input = sb.toString().replaceAll("\\s", "");
int boundary = 0;

while (boundary < input.length()) {
int treeBeginIndex = input.indexOf('(', boundary);
int treeEndIndex = treeBoundary(input, treeBeginIndex);

int sum = Integer.parseInt(input
.substring(boundary, treeBeginIndex));
String tree = input.substring(treeBeginIndex, treeEndIndex + 1);

if (treeSum(tree, sum)) {
System.out.println("yes");
} else {
System.out.println("no");
}

boundary = treeEndIndex + 1;
}
}

public static boolean treeSum(String tree, int sum) {
boolean retval = false;
Stack<SimpleEntry<Integer, String>> frontier = new Stack<SimpleEntry<Integer, String>>();
frontier.push(new SimpleEntry<Integer, String>(sum, tree));

SimpleEntry<Integer, String> current;
String currentTree, newTree;
int currentSum, newSum;

// Empty tree = ()
if (tree.length() == 2) {
return false;
}

while (!frontier.isEmpty()) {
current = frontier.pop();
currentSum = current.getKey();
currentTree = current.getValue();

// Empty tree = ()
if (currentTree.length() == 2) {
continue;
}

newSum = Integer.parseInt(currentTree.substring(1,
currentTree.indexOf('(', 1)));
newSum = currentSum - newSum;

newTree = currentTree.substring(currentTree.indexOf('(', 1),
currentTree.length() - 1);

// leaf node = ()()
if (newTree.equals("()()")) {
if (newSum == 0) {
retval = true;
break;
} else {
continue;
}
}

int boundary = treeBoundary(newTree);

String leftSubtree = newTree.substring(0, boundary + 1);
String rightSubtree = newTree.substring(boundary + 1);

rightSubtree));
leftSubtree));
}

return retval;
}

public static int treeBoundary(String tree) {
return treeBoundary(tree, 0);
}

public static int treeBoundary(String tree, int fromIndex) {
char[] treeArray = tree.toCharArray();

int i;
int counter = 0;

for (i = fromIndex; i < treeArray.length; i++) {
if (treeArray[i] == '(') {
counter++;
} else if (treeArray[i] == ')') {
counter--;
}

if (counter == 0) {
break;
}
}

return i;
}
}
``````
Last edited by dallen on Tue Apr 23, 2013 3:23 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: #112 Tree Summing TLE

Try using BufferedReader and BufferedWriter, or code in C++.
Check input and AC output for thousands of problems on uDebug!

dallen
New poster
Posts: 7
Joined: Mon Apr 22, 2013 1:06 am
Location: Asunción, Paraguay

### Re: #112 Tree Summing TLE

I've solved the TLE issue, reading all input before starting to do any computation was REALLY slow for large input. Now I'm getting WA, I've tried several test cases found in the following threads (browsed the forum a lot and found those test cases are more or less the same recommended in most threads).

- http://online-judge.uva.es/board/viewto ... f=1&t=8342
- http://online-judge.uva.es/board/viewto ... =1&t=75152
- http://online-judge.uva.es/board/viewto ... f=1&t=8546

I would really appreciate If anyone finds a test case that my code doesn't pass, or some tricky test cases to try. thanks.

Here's my code:

Code: Select all

``````//import java.io.File;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.AbstractMap.SimpleEntry;
import java.util.Scanner;
import java.util.Stack;

public class Main {

public static void main(String[] args) /*throws FileNotFoundException*/ {
//final long startTime = System.currentTimeMillis();

//System.setIn(new FileInputStream(new File("test6.txt")));

Scanner sc = new Scanner(System.in);

StringBuilder sb = new StringBuilder();
StringBuilder out = new StringBuilder();

while (sc.hasNextLine()) {
sb.append(sc.nextLine());
String tree = sb.toString();

int treeBeginIndex = tree.indexOf('(');

if (treeBeginIndex == -1 || treeBoundary(tree) == -1) {
continue;
}

int sum = Integer
.parseInt(tree.substring(0, treeBeginIndex).trim());
tree = tree.substring(treeBeginIndex);

if (treeSum(tree.replaceAll("\\s", ""), sum)) {
out.append("yes\n");
} else {
out.append("no\n");
}

sb.setLength(0);
}
System.out.println(out.toString());
//System.out.println(System.currentTimeMillis() - startTime);

}

public static boolean treeSum(String tree, int sum) {
boolean retval = false;
Stack<SimpleEntry<Integer, String>> frontier = new Stack<SimpleEntry<Integer, String>>();
frontier.push(new SimpleEntry<Integer, String>(sum, tree));

SimpleEntry<Integer, String> current;
String currentTree, newTree;
int currentSum, newSum;

// Empty tree = ()
if (tree.length() == 2) {
return false;
}

while (!frontier.isEmpty()) {
current = frontier.pop();
currentSum = current.getKey();
currentTree = current.getValue();

// Empty tree = ()
if (currentTree.length() == 2) {
continue;
}

newSum = Integer.parseInt(currentTree.substring(1,
currentTree.indexOf('(', 1)));
newSum = currentSum - newSum;

newTree = currentTree.substring(currentTree.indexOf('(', 1),
currentTree.length() - 1);

// leaf node = ()()
if (newTree.equals("()()")) {
if (newSum == 0) {
retval = true;
break;
} else {
continue;
}
}

int boundary = treeBoundary(newTree);

String leftSubtree = newTree.substring(0, boundary + 1);
String rightSubtree = newTree.substring(boundary + 1);

rightSubtree));
leftSubtree));
}

return retval;
}

public static int treeBoundary(String tree) {
char[] treeArray = tree.toCharArray();

int i;
int counter = 0;

for (i = 0; i < treeArray.length; i++) {
if (treeArray[i] == '(') {
counter++;
} else if (treeArray[i] == ')') {
counter--;
} else {
continue;
}

if (counter == 0) {
break;
}
}

// return -1 when the string is not a valid tree
if (counter != 0) {
i = -1;
}

return i;
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: #112 Tree Summing WA

You're printing an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

dallen
New poster
Posts: 7
Joined: Mon Apr 22, 2013 1:06 am
Location: Asunción, Paraguay

### Re: #112 Tree Summing WA

Thanks a lot brianfry713.. BTW, what a silly mistake.

angelblue15
New poster
Posts: 1
Joined: Sat Jul 27, 2013 9:51 am

### Re: #112 Tree Summing WA

Last edited by angelblue15 on Sat Oct 03, 2020 8:44 am, edited 1 time in total.
"Angle Blue"

Tiramisu
New poster
Posts: 8
Joined: Fri Feb 20, 2015 10:28 am

### Re: 112 - Tree Summing

removed code after AC
Last edited by Tiramisu on Sat Mar 28, 2015 12:09 am, edited 1 time in total.