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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Feb 16, 2005 10:13 am

try this input

INPUT

Code: Select all

5 ( 5 () 1 () ())
4 ( 2 (2 () 1()()) ())
what is your output??

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni » Wed Feb 16, 2005 11:06 am

Code: Select all

#define MAX 100
How about increasing this value to, say, 1000 or more.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Feb 17, 2005 7:00 am

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.
Last edited by ImLazy on Thu Feb 17, 2005 7:33 am, edited 1 time in total.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Feb 17, 2005 7:31 am

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!
I stay home. Don't call me out.

doddi
New poster
Posts: 2
Joined: Sun Mar 06, 2005 12:15 pm

Post by doddi » Sun Mar 06, 2005 12:22 pm

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
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni » Sun Mar 06, 2005 1:12 pm

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
New poster
Posts: 2
Joined: Sun Mar 06, 2005 12:15 pm

Post by doddi » Sun Mar 06, 2005 7:41 pm

Thanks teni_teni.

I thought that () should be considered as nodes. :oops:
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
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » Fri Apr 01, 2005 2:17 pm

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

Code: Select all

-50 ( -25
   )
   )
  ( -25(
)
(  )    
        )
)
"yes"
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » Fri Apr 01, 2005 2:20 pm

Hello all
I just get Acc :P
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 :wink:
Last edited by I LIKE GN on Fri Apr 29, 2005 5:24 pm, edited 1 time in total.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Apr 06, 2005 2:59 pm

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 :) /.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Thu Apr 07, 2005 4:35 pm

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
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Thu Apr 07, 2005 11:02 pm

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;
}
Understanding a problem in a natural way will lead to a natural solution

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni » Fri Apr 08, 2005 2:06 pm

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
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Tue Apr 12, 2005 8:41 am

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.
Understanding a problem in a natural way will lead to a natural solution

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

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

Post by Gaolious » Thu Jun 16, 2005 1:04 am

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

Post Reply

Return to “Volume 1 (100-199)”