Page 9 of 10

Posted: Sun Jan 06, 2008 12:00 am
by 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

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

Posted: Sat Jul 12, 2008 3:06 pm
by 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?

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

Posted: Sat Jul 12, 2008 9:34 pm
by x140l31
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

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

Posted: Sun Nov 09, 2008 11:19 am
by 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.

112

Posted: Sat Jul 17, 2010 3:32 pm
by 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.

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

Posted: Tue Jul 17, 2012 1:03 pm
by @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

112 WA

Posted: Sun Mar 10, 2013 5:25 am
by 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;
}

Re: 112 WA

Posted: Tue Mar 12, 2013 10:17 pm
by 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

#112 Tree Summing WA

Posted: Mon Apr 22, 2013 1:14 am
by 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;
	}
}

Re: #112 Tree Summing TLE

Posted: Mon Apr 22, 2013 11:36 pm
by brianfry713
Try using BufferedReader and BufferedWriter, or code in C++.

Re: #112 Tree Summing TLE

Posted: Tue Apr 23, 2013 2:58 am
by 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;
	}
}

Re: #112 Tree Summing WA

Posted: Wed Apr 24, 2013 1:30 am
by brianfry713
You're printing an extra blank line at the end.

Re: #112 Tree Summing WA

Posted: Wed Apr 24, 2013 3:41 am
by dallen
Thanks a lot brianfry713.. BTW, what a silly mistake.

Re: #112 Tree Summing WA

Posted: Sat Jul 27, 2013 9:54 am
by angelblue15
Yeah, I'm going to start over... thanks for the suggestions thus far..

Re: 112 - Tree Summing

Posted: Fri Mar 27, 2015 1:14 am
by Tiramisu
removed code after AC