Tutorial for Johnny and the Bean Stalk |
Each month we plan on taking one or two problems and describing various approaches to solve them. Since our first contest has just ended, I am going to describe the algorithm used to solve: http://www.codechef.com/MARCH09/problems/A2/
This problem is pretty simple, and there are two approaches to solving it. If you read the problem carefully, you will notice that you need to determine if the beanstalk (or tree) is valid. This is possible only when:
Approach-1 (Lowest to highest level):
1. The number of leaves on every level is at most the number of stems brought over from the previous level.
2. The tree will stop growing once there are no more stems. At the last level the number of stems is zero (they should all be leaves).
Approach-2 (Highest to lowest level):
1. The number of leaves at the last level is an even number (because the number of stems at any level will be twice the number of stems brought over from the previous level AND all stems at the last level will be converted to leaves).
2. If the tree is valid, at any level you can add the number of leaves plus the number of stems and divide by 2 to get an integer representing the number of stems brought over from the previous level.
For example (for the input 0,0,1,3,6) :
At level N (last level): For a valid tree, the number of leaves is even. In this case there are 6 leaves, the tree is valid so far.
At level N-1: The number of stems at this level will be 1/2 of 6 = 3. For a valid tree, the number of leaves at this level must be an odd number so that the sum of stems and leaves is even. In this case the number of leaves is 3, so the sum of stems (3) and leaves (3) is even (6) - the tree is valid so far.
At level N-2: The number of stems at this level will be 1/2 of 6 = 3. For a valid tree, the number of leaves at this level must be an odd number so that the sum of stems and leaves is even. In this case the number of leaves is 1, so the sum of stems (3) and leaves (1) is even (4) - the tree is valid so far.
At level N-3: The number of stems at this level will be 1/2 of 4 = 2. And so on...
3. To check the validity of your solution, ensure that the method above yields one stem in the first level.
Obviously, the first approach is much easier to follow, and also does not require you to store the entire contents of the input before you start processing it. This is what most of the contestants have done.
However, both solutions have the same complexity of O(n) and are valid and acceptable solutions for this contest.
Comments
wt does dis mean : The number
wt does dis mean : The number of leaves on every level is at most the number of stems brought over from the previous level.??
If u calculate the number of
If u calculate the number of stems for the next level then the number of leaves in the next level will be less than or equal to the number of stems in that level.
wait!, from level n to level
wait!, from level n to level n+1, first the stem doubles its number and some part of it converts to leaves? or some part of stems converts into leaves and then the rest doubles? which one is it?