Tutorial: Johnny and the Beanstalk (A2 Review)

1 min read

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.

5 Women Programmers Who Broke The Glass Ceiling

The gender bias in the coding world has been undeniable. The aptly named “brogramming” culture has made it challenging for women to rise in...
riddhi_225
2 min read

How Amit Upadhyay got placed at Cleartax

At CodeChef, we constantly stay in touch with CCDSAP holders to make the experience better for you and to fine-tune the certification. We spoke...
admin
1 min read

ACM ICPC Kolkata Regionals 2016 – Live Updates

Welcome to ACM ICPC Kolkata Regional 2016, the last leg regional before the India Final! Animesh and I will be giving you live updates throughout...
wittyceaser
2 min read

16 Replies to “Tutorial: Johnny and the Beanstalk (A2 Review)”

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

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

  3. 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?

  4. 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?

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

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

  7. The 3 Diablo has been released for a few days, so it is difficult to cultivate and to diablo 3 gold without D3 gold, Diablo 3 game players can hardly to level up their character, to help all games Diablo players get Diablo 3 Gold easier, I will share their experience of the cheap d3 gold farming tips 3 and strategies.
    c

  8. test cases of this question are very weak..
    even this code is accepted..

    #include
    #include
    using namespace std;

    int main()
    {
    int t,n,i;
    cin>>t;
    while(t–)
    {
    cin>>n;
    int a[n];
    int flag=0;
    int stem=1;
    int leaves;
    for(i=0;i>leaves;
    if(leaves>stem)
    {
    flag=1;
    break;
    }
    stem=(stem-leaves)*2;
    }
    if(flag||stem)
    {
    cout<<"No"<<endl;
    }
    else
    {
    cout<<"Yes"<<endl;
    }

    }

    return 0;

    }

  9. import sys
    import math

    t=int(input().strip())
    while(t>0):
    k=int(input().strip())
    l=list(map(int,input().strip().split(” “)))
    i,ns=0,1
    while(i=l[i]):
    ns=(ns-l[i])*2
    else:
    break
    i=i+1

    if(i==k and ns==0):
    print(“Yes”)
    else:
    print(“No”)
    t=t-1

    ———————————————————-
    Can anyone explain what is the problem with my code? I am getting “Time Limit” error for case 5 only!

Leave a Reply