112 - Tree Summing

[emotional blind]

try this input

INPUT

Code: Select all

5 ( 5 () 1 () ())
4 ( 2 (2 () 1()()) ())

what is your output??

[teni_teni]

Code: Select all

#define MAX 100

How about increasing this value to, say, 1000 or more.

[ImLazy]

From the input above, I get "yes yes". Certainly that's wrong answer. But I think your input is also wrong. It should be:

Code: Select all

5 ( 5 () ( 1 () ()))
4 ( 2 (2 () (1()())) ())

And I get "no no" on this input, that is the right answer.

[ImLazy]

Yes, you are right. I did a test just now. The test case of the Judge really has large amounts of nodes, more than 1000. And I change MAX to 2000, then get AC.
Thank you very much, my teni_teni!

[doddi]

Isn't xbeanx wrong here?
If I am correct

Code: Select all

77 (77(1()())())

and the last 9 strings should give "yes".

Code: Select all

77
(
	77
	(
		1
		()
		()
	)
	()
)

112 has been driving me crazy for the last couple of days, am I just misunderstanding something?

[teni_teni]

doddi, you maybe misunderstand the problem.

xbeanx's output is correct, since there is only one root-to-leaf path, 77 + 1.

another input for your help:

Code: Select all

77 (77(1()())())
77 (77  (1 () ())  (0 () ()) )
77 (77 () ())

my output:

Code: Select all

no
yes
yes

[doddi]

Thanks teni_teni.

I thought that () should be considered as nodes.
It works now and I put up some random strings to test it on.
If anybody is interested in them they can get them here and the answers here.

It doesn't have many traps, such as trees covering multiple lines or spaces but I hope it can help someone.

[I LIKE GN]

i tred with all inputs in the board
all are Correct
but Judge gives wa

Code: Select all

-50 ( -25
   )
   )
  ( -25(
)
(  )    
        )
)
"yes"

[I LIKE GN]

Hello all
I just get Acc
on the problem with a 12-line recursion code...
but i also wander why my previous soln. got wa.
the code was very large and the aproach was DIVIDE AND CONQUER
with link list tree handling...
So those who are trying to get acc... please look at the format

(INTEGER()())

The problem is really nice if u look at it with two nice eyes

[Sedefcho]

I am trying to solve the problem in Java.

My program currently gives the right answers for all
test cases in this thread. So most probably there's no major
LOGICAL BUG in my program.

I was first parsing the tree and then traversing it to check
if the given SUM can be formed.
The online judge was giving me TLE.

Then I did some optimizations which were basially that I now
keep a CurrentSum variable while parsing the S-Tree from
the input file. And every time I reach a leaf , I do a check
if the CurrentSum is equal to the SUM given in the
input ( the SUM which has to be formed ).

Anyway, the essense of my optimizations is not so important
( or mayb is ?! who knows ?! )

Now the Judge Gives me the following answer:

Code: Select all

Runtime Error  (SIGABRT)

And an email is sent to me containg this:

Code: Select all

Your program has died with signal 6 (SIGABRT). Meaning:

    Abort signal from abort()

Before crash, it ran during 6.104 seconds.

Note that I use JAVA. I think the Judge compiles the Java programs
to native code using GCJ ( a Java compiler for Linux which
compiles the Java programs to native code ).

Can anyone give me a hint of how can I fix my problem and
get ACC / or at least get a WA /.

[Sedefcho]

OK, I have fixed the problem which I describe in my previous post.

But ... Now I get TLE. I use Java as I said.



Important question:
Has someone managed to get this problem
ACC using Java as a programming language ?


If yes - I will be thankful if he/she gives me some tips
on how to optimize my Java Code.
I think my algorithm is not slow, I guess the performance problems
I have are in the String Processing techniques I use.
But it's just a guess.

[jakabjr]

OK, this is my code, shorter, processes everything in a string, hollds the current level and the sum so far on each level (the input is depth-first, so if 1 branch didn't give an answer, in won't anymore).
It also implement reading everithing w/o blanks, wich makes thing easier.
Problem is, though it works on tests that I've seen around, I get WA over&over.

IF ANYONE CAN TELL ME WAT'S WRONG, PLS DO SO!!!!!!

Code: Select all

#include <stdio.h>
#include <ctype.h>

char s[1000];
int n;

int leaf(int i){
	if (s[i]=='(' && s[i+1]==')' && s[i+2]=='(' && s[i+3]==')' ) return 1;
	return 0;
}

int check(void){
	int i, lev, sum[100], nr;

	sum[0]=lev=0;
	for(i=0;s[i]!='\0';i++){
		if(s[i]=='(') lev++;
		else if(s[i]==')') lev--;
		else {
			sscanf(s+i, "%d", &nr);
			sum[lev]=sum[lev-1]+nr;
			while((isdigit(s[i]) || s[i]=='-') && isdigit(s[i+1])) i++;
			if (sum[lev]==n && leaf(i+1)) return 1;
		}
	}
	return 0;
}

int main(){
	FILE *in;
	char ch;
	int i, lev;

	in = fopen("112.in","rb");

	while(fscanf(in, "%d ", &n)==1){
		i=lev=0;
		do{
			ch=fgetc(in);
			if (ch==' ' || ch=='\t' || ch=='\n' || ch=='\r') continue;
			s[i++]=ch;
			if (ch=='(') lev++;
			if (ch==')') lev--;
		}while(lev);
		s[i++]='\0';
		if (check()) printf("yes\n");
		else printf("no\n");
	}

	return 0;
}

[teni_teni]

It seems that some trees have 1000 or more nodes in the input of the Judge.
So, you should enlarge the size of the arrays, s[1000] and sum[100].

[jakabjr]

10x a lot, teni-teni, that got me AC and I guess I wouldn't have thought about that anytime soon.
So, as an answer to the topic, you can check out my solution, which runs pretty quick, anyway, faster than actually building the tree and going through it.

[Gaolious]

Please give me the test cases..

input

Code: Select all

22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) 
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) 
10 (3 
     (2 (4 () () ) 
        (8 () () ) ) 
     (1 (6 () () ) 
        (4 () () ) ) ) 
5 () 

0 () 
-1 (-1()()) 
77 (77(1()())()) 
-77 (-77()()) 

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()()) 
   ) ) ) 
      () ) () ) 

0 () 

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()())))) 
(6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()()))) 

0 (1() 
        (-2 () (1()()))) 

1 (1 () (0 ()()) ) 

0 (0 ()()) 

8(8(2(1()())())()) 
8(8(3(7()())())()) 
4(4(2(4()())())()) 
5(5(4()(1(7(3()())(4()()))(4(3()())())))()) 
21(7()(5()(5()(4(1(7()())())())))) 
47(7(9()(1(4()(7()(5(9(3(4(10()())())())(5(9(5(6(3(1(9()(2(3()(9(1(3(7()())(9()()))(9(5()(2()()))()))(7()())))(5(2()(6()(2()())))())))())(7()(2()(3()()))))(9()(10(4()(3()(4(3()(5()()))())))())))(3()()))())()))(6(10()())()))))()))()) 
24(9()(6()(1(2(9(8(7()())(1(1(7()())())(8()())))())(6(5(9()())())()))()))) 
15(8()(3(7(4(4()(9(6(3(3()())(9(3(3(8()())(7()()))())()))(3()()))()))())())(3(1(8(5(4(2()(4()(3(1()(10()(9()())))())))())(2()()))())())()))) 
18(4(9()())(1()(4()(9(3(9()(7()(8(6()())(5()(5()())))))(8(4()(1()()))()))())))) 
38 

(5 
  (6 
    (4 
      ()() 
    ) 
    (3 
      ()() 
    ) 
  ) 
  (7 
    (2 
      (1 
        ()() 
      ) 
      (10 
         () 
         (9 
           (5 
             ()() 
           ) 
           (2 
             ()() 
           ) 
         ) 
      ) 
    ) 
    () 
  ) 
) 
77 (77(1()())())
77 (77(1()())()) 
77 (77  (1 () ())  (0 () ()) ) 
77 (77 () ()) 
3 
(1 
  (1 (1 ()()) ()) 
  (2 ()       ()) 
) 

3 
(1 
  (1 (2 ()()) ()) 
  (2 ()       ()) 
)
5 ( 5 () 1 () ()) 
4 ( 2 (2 () 1()()) ())

output

Code: Select all

yes
no
yes
no
no
yes
no
yes
yes
no
yes
yes
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
yes
yes
no
no

ps. deleted my code...;;;;