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

Post Reply
*ClownPimp*
New poster
Posts: 4
Joined: Tue Jan 15, 2002 2:00 am
Contact:

Post by *ClownPimp* » Tue Jan 15, 2002 5:18 pm

Hmmm, anyone know the "trick" to solving this problem? My code works fine for the test data but fails the judge.

Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria

Post by Orgi » Tue Jan 15, 2002 5:57 pm

The task is simple.
All is said in the statement; the input might be very long; for example one separate test, possibly spread in lines, can be more than one thousand characters in all. I think this is the only 'trick' here.

Good luck.

*ClownPimp*
New poster
Posts: 4
Joined: Tue Jan 15, 2002 2:00 am
Contact:

Post by *ClownPimp* » Wed Jan 16, 2002 4:08 am

As far as I can see, my code can work for as much data as anyone cares to give it (as long as my long ints dont overflow). I was thinking that there might be some special case that is not very obvious and I fsiled to consider.

From what I read of the instructions, the only characters in the test data will be either numbers, whitespaces, or (, ). My program is recursive, so it seems that if it works for small trees, it will work for as big a tree as anyone cares to give it.

Also, I was wondering how the integer values are represented in the test data. My code assumes that the value, say 12, will not be a binary 12, but a '1' and a '2'. Is this correct? If not then this must be the reason my program failed.

Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:

Post by Cloud » Wed Jan 16, 2002 12:02 pm

can ur program handle negative numbers ?

*ClownPimp*
New poster
Posts: 4
Joined: Tue Jan 15, 2002 2:00 am
Contact:

Post by *ClownPimp* » Thu Jan 17, 2002 4:29 am

yup

*ClownPimp*
New poster
Posts: 4
Joined: Tue Jan 15, 2002 2:00 am
Contact:

Post by *ClownPimp* » Thu Jan 17, 2002 4:37 am

Doh! It doesnt actually. *bows head in shame*

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China

Post by idler » Thu Feb 21, 2002 4:27 pm

Any better solutions?
I use DFS to solve this problem, and my program ran for a pretty long time.
Here is my program(C++).
#ifndef ONLINE_JUDGE
#define ONLINE_JUDGE
#endif

#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>
#ifndef ONLINE_JUDGE
#include <stdio.h>
#endif

#define MAX_TREE_LEN 16384

// Basic Functions
bool is_valid(char ch)
{
return isdigit(ch) || ch == '(' || ch == ')' || ch == '-';
}

int find_rs(int s, const char *tree) // s is the position of first '('
{
int b_count = 1;
int i = s + 1;

while (b_count > 0)
{
if (tree == '(')
b_count++;
else
if (tree == ')') b_count--;

i++;
}

return i;
}

bool sub_dfs(int sum, int s, int e, const char *tree)
{
if (s + 1 == e) return false;

int ls, le, rs, re;
int num;

ls = s + 1;
num = atoi(&tree[ls]);

while (tree[ls] != '(') ls++;
rs = find_rs(ls, tree);
le = rs - 1;
re = e - 1;

if (sum == num && ls + 1 == le && rs + 1 == re)
return true;
else
return sub_dfs(sum - num, ls, le, tree) || sub_dfs(sum - num, rs, re, tree);
}

// Solution
void solve()
{
char tree[MAX_TREE_LEN];
int in_I;
char tmp;
int len;
int b_count; // brackets count

while (cin >> in_I)
{
do {cin >> tmp;} while (!is_valid(tmp));
tree[0] = tmp;

len = 1; b_count = 1;
while (b_count > 0)
{
do {cin >> tmp;} while (!is_valid(tmp));
tree[len++] = tmp;
if (tmp == '(')
b_count++;
else
if (tmp == ')') b_count--;
}
#ifndef ONLINE_JUDGE
tree[len] = '';
printf("I = %dn", in_I);
printf("Tree = %sn", tree);
#endif

if (len == 2)
cout << "non";
else
if (sub_dfs(in_I, 0, len - 1, tree))
cout << "yesn";
else
cout << "non";
}
}

int main()
{
solve();

return 0;
}

0.710sec and 4xxK bytes.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Fri Mar 01, 2002 2:40 pm

I got WA,but I don't know why I got WA.I've checked on my code and run several test case I made myself.
Anyway,what's the answer for 0 ()??(I've tried "yes",and "no",both WA)
And is there any special test case??
Here is my code,but I think It's no need to look into it.


Code: Select all

#include <stdio.h>
#include <stdlib.h>

class tree
{
public:
	int num;
	tree *left;
	tree *right;
};

int num;
tree* head=NULL;

int maket(tree* ptr)
{
	char tmp;
	int flag=0;
	int tn=0;
	int result=0;
	while(1)
	{
		do
		{
			tmp=getchar();
		}while(tmp==' '||tmp=='n');
		if(tmp>=48&&tmp<=57)
		{
			tn=tn*10+tmp-48;
			if(flag==0)
				flag=1;
		}
		else if(tmp==')')
		{
			if(flag==0)
				return 0;
			else if(flag==3)
				return 1;
			tn=0;
		}
		else if(tmp=='(')
		{
			if(flag==1)
			{
				ptr->num=tn;
				ptr->left=(tree *)malloc(sizeof(tree));
				ptr->left->left=NULL;
				ptr->left->right=NULL;
				ptr->left->num=0;
				result=maket(ptr->left);
				if(result==0)
				{
					free(ptr->left);
					ptr->left=NULL;
				}
				flag=2;
			}
			else if(flag==2)
			{
				ptr->num=tn;
				ptr->right=(tree *)malloc(sizeof(tree));
				ptr->right->left=NULL;
				ptr->right->right=NULL;
				ptr->right->num=0;
				result=maket(ptr->right);
				if(result==0)
				{
					free(ptr->right);
					ptr->right=NULL;
				}
				flag=3;
			}
		}
	}
}

int count(tree* ptr,int now)
{
	int result=0;
	now=now+ptr->num;
	if(ptr->left==NULL&&ptr->right==NULL)
		if(now==num)
			return 1;
	if(ptr->left!=NULL)
	{
		result=count(ptr->left,now);
		if(result==1)
			return 1;
	}
	if(ptr->right!=NULL)
	{
		result=count(ptr->right,now);
		if(result==1)
			return 1;
	}
	return 0;
}

void cleantree(tree *ptr)
{
	if(ptr->left!=NULL)
		cleantree(ptr->left);
	if(ptr->right!=NULL)
		cleantree(ptr->right);
	ptr->left=NULL;
	ptr->right=NULL;
	free(ptr);
	ptr=NULL;
}

void main()
{
	char tmp;
	int tn;
	int flag=0;
	int result=0;
	while(scanf("%d",&num)!=EOF)
	{
		head=NULL;
		flag=0;
		tn=0;
		while(1)
		{
			do
			{
				tmp=getchar();
			}while(tmp==' '||tmp=='n');
			if(tmp>=48&&tmp<=57)
			{
				tn=tn*10+tmp-48;
				if(flag==0)
					flag=1;
			}
			else if(tmp==')')
			{
				if(flag==0)
				{
					if(num==0)
						printf("yesn");
					else
						printf("non");
					free(head);
					break;
				}
				else if(flag==3)
				{
					result=count(head,0);
					if(result==1)
						printf("yesn");
					else
						printf("non");
					cleantree(head);
					break;
				}
				tn=0;
			}
			else if(tmp=='(')
			{
				if(flag==1)
				{
					head=(tree *)malloc(sizeof(tree));
					head->left=NULL;
					head->right=NULL;
					head->num=tn;
					head->left=(tree *)malloc(sizeof(tree));
					head->left->left=NULL;
					head->left->right=NULL;
					head->left->num=0;
					result=maket(head->left);
					if(result==0)
					{
						free(head->left);
						head->left=NULL;
					}
					flag=2;
				}
				else if(flag==2)
				{
					head->right=(tree *)malloc(sizeof(tree));
					head->right->left=NULL;
					head->right->right=NULL;
					head->right->num=0;
					result=maket(head->right);
					if(result==0)
					{
						free(head->right);
						head->right=NULL;
					}
					flag=3;
				}
			}
		}
	}
}

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Tue Mar 05, 2002 5:47 am

A tree with just zero has no paths so the answer is no. The other special cases I can think of are possibility of empty branches [i.e. ()()], the possibility of non-positive values [i.e. 0,-1,..etc], and ofcourse, the most OBVIOUS, making sure you are traversing from root to leaf and not just stopping in the middle.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed Mar 06, 2002 4:30 am

Try this testcase: 9 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))

Btw, your program is huge. Try to not build the tree explicitly but to only traverse it on the fly while reading the input.

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

Post by ram » Wed Mar 06, 2002 9:24 am

Here is my code:

Its doesnt built tree but only traverses through the input and find the result. Its working absoultely fine with the test cases. online judge reports "Time Limit exceeded"


Can anyone help me out? :sad:

@BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <vector>
#include <numeric>
#include <stdio.h>


using namespace std;

int main()
{

char ch;
bool ans,end;
int sumtot;
vector<char> bracs;
vector<int> vals;
FILE *fp;
fp = stdin;
//fp= fopen("temp1.txt","r");

while(fscanf(fp,"%d",&sumtot))
{
int num,popimid;

end=false;
ans=false;
bracs.erase(bracs.begin(),bracs.end());
vals.erase(vals.begin(),vals.end());
ch='-';

while(true)
{

while(ch!='(')
{ if(ch==')')
{
bracs.pop_back();
vals.pop_back();
if (bracs.size()<=0){
end=true;
break;}
}
fscanf(fp,"%c",&ch);

}

if(end) break;
bracs.push_back(ch);
fscanf(fp,"%c",&ch);
while(ch==' ')
fscanf(fp,"%c",&ch);

if(ch==')')
{
popimid ++;
bracs.pop_back();
if(bracs.size()==0) break;
if(popimid==2) {
num=accumulate(vals.begin(),vals.end(),0);
if(num == sumtot)
{ ans=true;
while(bracs.size()!=0)
{
fscanf(fp,"%c",&ch);
if(ch=='(')
bracs.push_back(ch);
else
{if(ch==')')
bracs.pop_back();
}
}

break;
}
popimid=0;
}
fscanf(fp,"%c",&ch);
}
else
{
num=0;
while(ch>='0'&&ch<='9')
{
num*=10;
num+=ch-'0';
fscanf(fp,"%c",&ch);
// if(ch!='(')cout<<ch;

}
// cout<<num<<endl;
popimid=0;
vals.push_back(num);
}

}

cout<<(ans?"yes":"no")<<endl;

}

return 0;

}
@END_OF_SOURCE_CODE

junyu
New poster
Posts: 3
Joined: Wed Mar 06, 2002 2:00 am

Post by junyu » Wed Mar 06, 2002 3:26 pm

I checked my codes several days.
I think that it's correct,but I received WA
and WA and WA...><...
I don't know what's wrong with my codes.
All cases consist of positive integers,
negative integers,and 0 () are all correct..
Can you help me...
I really need your help....

/* @JUDGE_ID: 17563KJ 112 C */
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

main(){

int find_left, done, goal, test[2000][2];
char newchar;
char str[100];
int k, newnum, minus, i, j, amount, left, right;

#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif

while ( scanf("%d",&goal) != EOF ){

for( k = 0 ; k < 2000 ; k++ )
{
test[k][0] = -1;
test[k][1] = -1;
}

left = 0;
right = 0;

newchar = getc(stdin);
left = left + 1;
find_left = 1;
minus = 0;

while ( newchar != '(' ){
newchar = getc(stdin);
} /*read the first ( */

for( k = 0; k < 100; k++ ){
str[k]=' ';
}

while(left != right){
newchar = getc(stdin);
if( newchar == '(' ){
if( str[0] != ' ' ){
for(k=0;k<100;k++){
if( str[k] == ' ' ){
str[k] = '';
}
}
if( minus == 1){
minus = 0;
newnum = 0-atoi(str);
}else if( minus == 0 ){
newnum = atoi(str);
}
for( k = 0 ;k < 2000; k++ ){
if(test[k][1] == -1){
test[k][0]=newnum;
test[k][1]=left-right;
break;
}
}
for( k = 0; k < 100; k++ ){
str[k] = ' ';
}
}

left = left + 1;
find_left = 1;

}else if(newchar == ')'){

if(find_left == 1){

for(k = 0; k < 2000; k++ ){
if(test[k][1]==-1){
test[k][0]=0;
test[k][1]=0;
break;
}
}
}
right = right + 1;
find_left = 0;

}else if( newchar<='9' && newchar >='0'){
for( k = 0; k < 100; k++){
if(str[k] == ' '){
str[k] = newchar;
break;
}
}
find_left = 0;
}else if(newchar == '-'){
minus = 1;
find_left = 0;
}

}

done = 0;
for ( k = 0;k < 2000; k++ ){
if(done == 1){
break;
}
if( test[k][1] == -1 ){
break;
}else if( test[k][1]!=0 && test[k+1][1]==0 && test[k+2][1]==0){
amount = 0;
j = test[k][1];

for( i = k ;i >= 0; i-- ){
if(test[1] == j){
amount = amount+test[0];
j = j - 1;
if( amount==goal && j==0){
done=1;
break;
}
}
}
}
}
if ( done == 0 ){
printf("non");
}else if( done == 1 ){
printf("yesn");
}
}
}

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Wed Mar 06, 2002 5:22 pm

I got no for the input 9 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
I think it's right,isn't it?
However,I'm going to try another mailbox,Hotmail have fooled me several times :sad:

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

Post by ram » Wed Mar 06, 2002 10:38 pm

Can your code tackle spaces at any point in the input???

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Mar 07, 2002 2:38 am

I know it is faster to do it on the fly, but I would like to know why my tree building code gives me WA.

Code: Select all

#include <stdio.h>

struct Node
{
	Node *up;
	Node *left;
	Node *right;
	int value;
};

void Discard()
{
	scanf("%*[^-0-9()]");
}

char Peek()
{
	return ungetc(getc(stdin),stdin);
}

bool isParen()
{
	char P;
	P=Peek();
	return P=='('||P==')';
}

bool Traverse(Node *Root,int Target,int Sum)
{
	if(!Root)
	{
		return false;
	}

	Sum+=Root->value;

	if(Root->left==NULL&&Root->right==NULL)
	{
		return Target==Sum;
	}

	return Traverse(Root->left,Target,Sum) || Traverse(Root->right,Target,Sum);
}

void main()
{
	int T,i,k,n;
	Node *Root,*Current;
	char c;
	bool D[100],L[100];

	while(scanf("%d",&T)!=EOF)
	{
		//printf("%d: ",T);

		Root=new Node;
		Root->up=NULL;
		Root->left=NULL;
		Root->right=NULL;
		Current=Root;

		k=1;
		for(i=0;i<100;i++)
		{
			L[i]=false;
			D[i]=true;
		}
		Discard();
		scanf("%c",&c);
		while(k>0)
		{
			Discard();
			if(isParen())
			{
				scanf("%c",&c);
				if(c=='(')
				{
					k++;
					L[k-1]=false;
					if(D[k-1])
					{
						Current->left=new Node;
						Current->left->up=Current;
						Current=Current->left;
						//printf("Create leftn");
					}
					else
					{
						Current->right=new Node;
						Current->right->up=Current;
						Current=Current->right;
						//printf("Create rightn");
					}
					Current->left=NULL;
					Current->right=NULL;
				}
				else
				{
					k--;
					if(k>0)
					{
						Current=Current->up;
						if(!L[k])
						{
							if(D[k])
							{
								delete Current->left;
								Current->left=NULL;
								//printf("Delete leftn");
							}
							else
							{
								delete Current->right;
								Current->right=NULL;
								//printf("Delete rightn");
							}
						}
						else
						{
							//printf("Shift upn");
						}
						D[k]=!D[k];
					}
				}
			}
			else
			{
				scanf("%d",&n);
				Current->value=n;
				L[k-1]=true;
				if(k>1)
					L[k-2]=true;
				//printf("Assign %dn",n);
				//printf("%d ",n);
			}
		}
		if(!L[0])
			Root=NULL;
		if(Root)
		{
			if(Traverse(Root,T,0))
				printf("yesn");
			else
				printf("non");
		}
		else
		{
			printf("non");
		}
		delete Root;
	}
}

Post Reply

Return to “Volume 1 (100-199)”