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

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

Post by asmaamagdi » Sun Jan 06, 2008 12:00 am

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.

Post by Samiul » Sat Jul 12, 2008 3:06 pm

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.

Post by x140l31 » Sat Jul 12, 2008 9:34 pm

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.

Post by 1989gaurav » Sun Nov 09, 2008 11:19 am

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

Post by sarker306 » Sat Jul 17, 2010 3:32 pm

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
Location: Chittagong, Bangladesh

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

Post by @li_kuet » Tue Jul 17, 2012 1:03 pm

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

Post by jsimister » Sun Mar 10, 2013 5:25 am

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;
}

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

Re: 112 WA

Post by brianfry713 » Tue Mar 12, 2013 10:17 pm

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

Post by dallen » Mon Apr 22, 2013 1:14 am

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.

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

Re: #112 Tree Summing TLE

Post by brianfry713 » Mon Apr 22, 2013 11:36 pm

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

Post by dallen » Tue Apr 23, 2013 2:58 am

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);

			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;
	}
}

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

Re: #112 Tree Summing WA

Post by brianfry713 » Wed Apr 24, 2013 1:30 am

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

Post by dallen » Wed Apr 24, 2013 3:41 am

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

Post by angelblue15 » Sat Jul 27, 2013 9:54 am

Yeah, I'm going to start over... thanks for the suggestions thus far..
"Angle Blue"

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

Re: 112 - Tree Summing

Post by Tiramisu » Fri Mar 27, 2015 1:14 am

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

Post Reply

Return to “Volume 1 (100-199)”