112 - Tree Summing
Moderator: Board moderators
-
- 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
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
Asmaa Magdi
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?
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.
Re: Prob 112. Tree Summing, I got TLE.
you don't need this arraySamiul 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?
this problem can be solved in O(n) while reading the input with a recursive function
-
- 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.
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.
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
'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
should not the value in level be 1?
That's all I can think of.
Any kind of help will be appreciated.
Thanks.
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;
}
Code: Select all
if(Sum_level && Sum_level<2 && child==2) flag=0, Sum_level=0;
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
( )
That's all I can think of.
Any kind of help will be appreciated.
Thanks.
Re: 112. please, give me the test cases,..
Try this Input :
Output should be :
Code: Select all
5 (18 (-
13 ( )( ) )( ) )
0 ( 1
()(- 2 ( ) ( 1 ()() ) )
)
0 ( )
Code: Select all
yes
yes
no
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 == ')');
*read = (c - s);
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 112 WA
Input:Output should be:
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()()))))
Code: Select all
yes
yes
yes
yes
Check input and AC output for thousands of problems on uDebug!
#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);
frontier.add(new SimpleEntry<Integer, String>(new Integer(newSum),
rightSubtree));
frontier.add(new SimpleEntry<Integer, String>(new Integer(newSum),
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.
-
- 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!
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:
- 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);
frontier.add(new SimpleEntry<Integer, String>(new Integer(newSum),
rightSubtree));
frontier.add(new SimpleEntry<Integer, String>(new Integer(newSum),
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;
}
}
-
- 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!
Re: #112 Tree Summing WA
Thanks a lot brianfry713.. BTW, what a silly mistake.
-
- New poster
- Posts: 1
- Joined: Sat Jul 27, 2013 9:51 am
Re: #112 Tree Summing WA
Yeah, I'm going to start over... thanks for the suggestions thus far..
"Angle Blue"
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.