Tree Product

Problem code: TPRODUCT

All submissions for this problem are available.

Given a complete binary tree with the height of H, we index the nodes respectively top-down and left-right from 1. The i-th node stores a positive integer Vi. Define Pi as follows: Pi=Vi if the i-th node is a leaf, otherwise Pi=max(Vi*PL, Vi*PR), where L and R are the indices of the left and right children of i, respectively. Your task is to caculate the value of P1.

Input

There are several test cases (fifteen at most), each formed as follows:

  • The first line contains a positive integer H (H ? 15).
  • The second line contains 2H-1 positive integers (each having a value of 109 at most), the i-th integer shows the value of Vi.
The input is ended with H = 0.

Output

For each test case, output on a line an integer which is the respective value of P1 found, by modulo of 1,000,000,007.

Example

Input:
2
1 2 3
3
3 1 5 2 6 4 7
0

Output:
3
105
Explanation:
The second test case is constructed as follows: 

     3
    / \
   /   \
  1     5
 / \   / \
2   6 4   7
Author: anhdq
Date Added: 21-02-2011
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

is there something wrong in

amnsinghl @ 1 May 2011 08:23 PM

is there something wrong in the question

as i m getting wrong answer again and again

Question should have been

mysticmonk @ 2 May 2011 01:06 AM

Question should have been like - "Given a perfect binary tree" instead of "Given a complete binary tree". Makes difference.

 

Reference : http://en.wikipedia.org/wiki/Binary_tree

i am using Java platform

biraj_patel @ 2 May 2011 02:04 AM

i am using Java platform ,getting correct answers on compiler still it shows wrong answer. I have checked from testcases 0 to 3 (higher will be difficult to check ) . Still WRONG ANSWER any reason ??

@kostia and karanveer  did

vfix @ 2 May 2011 02:05 AM

@kostia and karanveer  did you guys realized that you are participating in a competition?

comments are provided for making any announcements by admins or clearing someone's doubtes related TO A PART OF PROBLEM STATEMENT WHICH IS NOT CLEAR,NOT  FOR DISCUSSING POTENTIAL SOLUTIONS.Be careful next time

@Kostia hey i am not getting

biraj_patel @ 2 May 2011 02:06 AM

@Kostia hey i am not getting significance of this 1000000007 number ..we just have to put % sign on final answer right ?

@Patel : right

mysticmonk @ 2 May 2011 02:32 AM

@Patel : right

can someone point me to page

mysticmonk @ 2 May 2011 04:34 AM

can someone point me to page which tell me how to submit solutions written in java? Earlier, I think I had seen a page which talked about creating a jar file, but now,  I am not able to find it.

@chetan : solutions written

shankysodhi @ 2 May 2011 09:51 AM

@chetan : solutions written in java are not complicated .... they should just have the name of the class as "Main" .. note capital M  ....  and write the main functionality in public static void main function ......

is there is a need of loop

rijin @ 2 May 2011 05:36 PM

is there is a need of loop for test case;

use to read no of testcases?

is it just a "complete binary

gopi6sigma @ 2 May 2011 05:39 PM

is it just a "complete binary tree" or a "Perfect/full binary" tree ??????????????

@govardhan

rajneesh2k10 @ 2 May 2011 06:11 PM

@govardhan reddy:

@Chetan:

Problem statement is quite sufficient to guess what kind of tree its talking about. Read carefully! If the above tree falls under the category of perfect binary tree the obviously it is a complete binary tree as all perfect binary trees are complete binary trees (inherently by definition. See definition here: http://en.wikipedia.org/wiki/Binary_tree )! :) :)

@AUTHOR : Where to take MOD

theeporithirumugam @ 2 May 2011 07:39 PM

@AUTHOR : Where to take MOD ?

MOD only in Final Step or i Can use MOD for each max ( .....) calculations ?

@RIJIN: yes ... there is  ...

shankysodhi @ 2 May 2011 08:17 PM

@RIJIN: yes ... there is  ... the program runs only once .... and it should cover all the testcases ...

I got some RTEs because of

zobayer @ 2 May 2011 11:56 PM

I got some RTEs because of using PrintWriter class in Java, I don't know the reason why it will get RTE. When I change it to normal System.out, it got AC. What I am missing here?

@Admin: my program is workin

rushilpaul @ 3 May 2011 03:40 AM

@Admin: my program is workin correctly for a "perfect binary tree"..i have tried till H=4 (more than that becomes too long) & my solution is absolutely correct

then y is your system declarin it as wrong?? There cant be "tricky handcrafted" test cases for this question too..

my algo is a very simple 1..so no scope for mistakes too..

@Rushil: Same here...dont

vikram535 @ 3 May 2011 02:20 PM

@Rushil: Same here...dont know why it is giving wrong answer every time....I have tried so many times

@Admin, Same is the problem

harishp @ 3 May 2011 03:30 PM

@Admin,

Same is the problem with me too. My program also works fine and my algo pretty much direct. No complicated logic is involved. Then why is it showing wrong answer everytime?

Getting Wrong Answer

bharswami @ 3 May 2011 08:29 PM

Getting Wrong Answer everytime. Logic is perfect and straightforward. Any suggestions?

I get WA..Is there any hint

rauf @ 3 May 2011 09:30 PM

I get WA..Is there any hint about this problem.

@admin: plz read the above

rushilpaul @ 4 May 2011 12:49 AM

@admin: plz read the above posts man n tell us what's happening...

You will not be given hints

triplem @ 4 May 2011 02:31 AM

You will not be given hints during a competition.

Could you give us additional

bharswami @ 4 May 2011 06:49 AM

Could you give us additional test cases please. Larger ones if possible

If simple logic is not

manoharsingh23 @ 4 May 2011 01:04 PM

If simple logic is not working . Think Something difficult :)

Its simple tree traversal

rupeshpaikara @ 4 May 2011 03:51 PM

Its simple tree traversal problem...... Buts its giving wrong answer....... something is wrong with the judge....

@admin Please provide us some

rupeshpaikara @ 4 May 2011 03:54 PM

@admin Please provide us some more test cases .....

no idea why i get a runtime

hardfire_avk @ 4 May 2011 10:41 PM

no idea why i get a runtime error time and again !

No reason for a wrong

crooked_coder @ 5 May 2011 09:25 AM

No reason for a wrong answer.

@Admin : there is something wrong with the judge !

Sorry judge, got the right

crooked_coder @ 5 May 2011 11:24 AM

Sorry judge, got the right answer. Awesome problem though that caused WA ;-)

wat we should do for the

classic_gautham @ 5 May 2011 11:55 AM

wat we should do for the conditons h>15

@gautham at codechef assume

sak3t @ 5 May 2011 04:15 PM

@gautham

at codechef assume inputs are correct i.e within input limits

what is the ans

raulrag009 @ 5 May 2011 06:24 PM

what is the ans for

2

1000000000 999999999 999999998

 

???

As the value range of the ith

adu101992 @ 5 May 2011 08:33 PM

As the value range of the ith integer is 10^9

then what is the need to find the modulo with respect to 1,000,000,007 when this value is greater than 10^9.

it makes no difference as 10^9%1,000,000,007 is again 10^9

Aditya : What if u  have 10^9

raulrag009 @ 5 May 2011 09:56 PM

Aditya : What if u  have 10^9 as two leaf nodes  in a  tree of height 2 and the root  node's value  is 10^9-1

 

U gotta multiply them  right , there u have to do some thing with modulo , so that u can control the over flow

modulo operation is not

ashishnegi001 @ 8 May 2011 01:00 PM

modulo operation is not available on doubles ...

should we try subtracting the divisor from the dividend again and again till we find the remainder

Even I'm stuck with the

angad619 @ 8 May 2011 02:17 PM

Even I'm stuck with the modulo thing. Soln gives correct ans for given test cases. It says wrong answer when I submit.

Urrgh! This is so irritating..

I dont get the whole " For

Myth17 @ 8 May 2011 04:16 PM

I dont get the whole " For each test case, output on a line an integer which is the respective value of P1 found, by modulo of 1,000,000,007. "

Could this be explained now or later when the contest ends.

can you please tell me

vickysirwani @ 8 May 2011 09:17 PM

can you please tell me whether we have to do the modulo for each step or just for the final answer?

plzzz put some good test case

aayush123 @ 8 May 2011 10:19 PM

plzzz put some good test case .

@nitish & vicky: that

rushilpaul @ 9 May 2011 01:20 AM

@nitish & vicky: that statement means output P1 % 1000000007 to stdout,

and if you do this at each step, it prevents an overflow.

Solutions in F# are Extremely

wRabbits @ 9 May 2011 04:48 AM

Solutions in F# are Extremely slow, have to rewrite to some other language

Guys, this is a contest. I

Amlesh @ 9 May 2011 05:57 PM

Guys, this is a contest. I don't think you should be pestring the admin with the problem statement, as part of the the problem is understanding the statement. As for the problems you have been having, I bet it's something you are overlooking (currently, I believe I might be having a similar problem).

Just a quick note: since the

Amlesh @ 9 May 2011 06:03 PM

Just a quick note: since the height goes up to 15, and since each of the numbers can go upto 10^9, technically P[1] can go upto 10^(9*14) = 10^126, which is way too big to handle without a 'biginteger' class, or somethign of that sort.

My answers are coming correct

yash_vohra @ 10 May 2011 01:32 AM

My answers are coming correct on my machine and exactly in same format. But still the the judge says "wrong output".

Please help!!

This is frustrating..I am

yash_vohra @ 10 May 2011 01:51 AM

This is frustrating..I am using exactly same options while compiling te code on my machine as given in FAQs, still the judge here says wrong optput everytime. I have tested my output upto level 6 and it is just correct.

I've also taken care of output format and am using simple cin and cout for input output in c++ code.

Can anyone tell me the possible reson for it??

@Yash: you are overlooking

rushilpaul @ 10 May 2011 10:14 PM

@Yash: you are overlooking something man. Think about how the others are getting their code accepted by the judge..its a bit tricky ;-)

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions