Tutorial: Johnny and the Beanstalk (A2 Review)

Posted by dhruv.m on March 17th, 2009 Filed in Tutorials View Comments

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.

  • Share/Bookmark
  • Deepak S Patwardhan

    I like the problem and let me rephrase it from a data structures point of view (for what its worth).

    Problem : You are given the height of a full binary tree, and a sequence of numbers, which is claimed to be the number of leaves at each level, starting from the top. You have to verify that claim is theoretically possible.

    Approach 1: Grow a tree.
    Start with a single node, and grow the tree in order to satisfy the alleged number of leaves at each level, starting at top. If the claim is wrong, you’ll either be unable to satisfy at a certain level (because the claim is too big), or will be left with extra leaves at the end. (claim was too small)

    Approach 2: Prune a tree. (not eco-friendly)
    Given the number of leaves at the bottom of the tree, cut them to increase the number of leaves at the previous level and decrease the height of the tree. Iterate. If the claim is wrong, you’ll either reach a level with odd number of leaves or end up with a zero height tree with more than one node.

    **

    Its interesting to see the the variation in runtimes, within the same language, of course. With my best efforts, I couldn’t bring my runtime (14) anywhere close to the best, which is just less than 0.4.

    If I/O is the reason behind it, I guess this is my first hand experience of how slow I/O can be, if you don’t take care of it.

  • Deepak S Patwardhan

    I like the problem and let me rephrase it from a data structures point of view (for what its worth).

    Problem : You are given the height of a full binary tree, and a sequence of numbers, which is claimed to be the number of leaves at each level, starting from the top. You have to verify that claim is theoretically possible.

    Approach 1: Grow a tree.
    Start with a single node, and grow the tree in order to satisfy the alleged number of leaves at each level, starting at top. If the claim is wrong, you’ll either be unable to satisfy at a certain level (because the claim is too big), or will be left with extra leaves at the end. (claim was too small)

    Approach 2: Prune a tree. (not eco-friendly)
    Given the number of leaves at the bottom of the tree, cut them to increase the number of leaves at the previous level and decrease the height of the tree. Iterate. If the claim is wrong, you’ll either reach a level with odd number of leaves or end up with a zero height tree with more than one node.

    **

    Its interesting to see the the variation in runtimes, within the same language, of course. With my best efforts, I couldn’t bring my runtime (14) anywhere close to the best, which is just less than 0.4.

    If I/O is the reason behind it, I guess this is my first hand experience of how slow I/O can be, if you don’t take care of it.

  • zootzoot

    There is also a mathematical way of solving this problem. If you have input with 3 levels (example 0 1 2):

    level1 * 2^2 +
    level2 * 2^1 +
    level3 * 2^0
    =
    2^(num of levels – 1)

    The same principle can be applied to any number of levels.

    I have tested my solution for the Beanstalk problem against test data validated using the above formula, but it still says my answer is wrong?

  • zootzoot

    There is also a mathematical way of solving this problem. If you have input with 3 levels (example 0 1 2):

    level1 * 2^2 +
    level2 * 2^1 +
    level3 * 2^0
    =
    2^(num of levels – 1)

    The same principle can be applied to any number of levels.

    I have tested my solution for the Beanstalk problem against test data validated using the above formula, but it still says my answer is wrong?

  • zootzoot

    PS. You have to exclude any input that has the highest level of a 0.

  • zootzoot

    PS. You have to exclude any input that has the highest level of a 0.

  • JensenDP

    zootzoot, I don’t quite understand what you mean by an “input that has the highest level of a 0″. Can you give an example?

  • JensenDP

    zootzoot, I don’t quite understand what you mean by an “input that has the highest level of a 0″. Can you give an example?

  • Deepak S Patwardhan

    I like the problem and let me rephrase it from a data structures point of view (for what its worth).Problem : You are given the height of a full binary tree, and a sequence of numbers, which is claimed to be the number of leaves at each level, starting from the top. You have to verify that claim is theoretically possible.Approach 1: Grow a tree.Start with a single node, and grow the tree in order to satisfy the alleged number of leaves at each level, starting at top. If the claim is wrong, you'll either be unable to satisfy at a certain level (because the claim is too big), or will be left with extra leaves at the end. (claim was too small)Approach 2: Prune a tree. (not eco-friendly)Given the number of leaves at the bottom of the tree, cut them to increase the number of leaves at the previous level and decrease the height of the tree. Iterate. If the claim is wrong, you'll either reach a level with odd number of leaves or end up with a zero height tree with more than one node.**Its interesting to see the the variation in runtimes, within the same language, of course. With my best efforts, I couldn't bring my runtime (14) anywhere close to the best, which is just less than 0.4.If I/O is the reason behind it, I guess this is my first hand experience of how slow I/O can be, if you don't take care of it.

  • Deepak S Patwardhan

    I like the problem and let me rephrase it from a data structures point of view (for what its worth).

    Problem : You are given the height of a full binary tree, and a sequence of numbers, which is claimed to be the number of leaves at each level, starting from the top. You have to verify that claim is theoretically possible.

    Approach 1: Grow a tree.
    Start with a single node, and grow the tree in order to satisfy the alleged number of leaves at each level, starting at top. If the claim is wrong, you'll either be unable to satisfy at a certain level (because the claim is too big), or will be left with extra leaves at the end. (claim was too small)

    Approach 2: Prune a tree. (not eco-friendly)
    Given the number of leaves at the bottom of the tree, cut them to increase the number of leaves at the previous level and decrease the height of the tree. Iterate. If the claim is wrong, you'll either reach a level with odd number of leaves or end up with a zero height tree with more than one node.

    **

    Its interesting to see the the variation in runtimes, within the same language, of course. With my best efforts, I couldn't bring my runtime (14) anywhere close to the best, which is just less than 0.4.

    If I/O is the reason behind it, I guess this is my first hand experience of how slow I/O can be, if you don't take care of it.

  • EkramPrashanta

    In ffice right now will go through this latter.respectjames______________________________________________Buy Aion Kinah | Cheap Aion kinah

  • EkramPrashanta

    In ffice right now will go through this latter.

    respect
    james
    ______________________________________________
    Buy Aion Kinah | Cheap Aion kinah

blog comments powered by Disqus

Programmer of the Month

Name : Anton Lunyov
Age : 23 yrs
Inst/Company : Institute of Applied Mathematics and Mechanics of National Academy of Science of Ukraine
Userid : anton_lunyov

Find out more about the person behind the username anton_lunyov

    Recent Posts

    Categories

    Recent Comments

    Recent Pictures

    Blogroll

    Archives

    Company Blogs

    Careers@Directi