112 - Tree Summing

[*ClownPimp*]

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

[Orgi]

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*]

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]

can ur program handle negative numbers ?

[*ClownPimp*]

yup

[*ClownPimp*]

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

[idler]

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]

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]

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]

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]

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?

@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]

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]

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

[ram]

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

[C8H10N4O2]

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