112 - Tree Summing

[asmaamagdi]

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

[Samiul]

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?

[x140l31]

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]

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]

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]

Try this Input :

Code: Select all

5 (18  (-  
          13  ( )( ) )( )   )
0 (  1
           ()(-  2 ( ) ( 1 ()() ) )
  )
0 (                         )

Output should be :

Code: Select all

yes
yes
no

[jsimister]

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]

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

[dallen]

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

[brianfry713]

Try using BufferedReader and BufferedWriter, or code in C++.

[dallen]

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]

You're printing an extra blank line at the end.

[dallen]

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

[angelblue15]

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

[Tiramisu]

removed code after AC