How can I develop the exact recurrence for this?

Question

N buildings are built in a row, numbered 1 to N from left to right. Spiderman is on buildings number 1, and want to reach building number N. He can jump from building number i to building number j iff i < j and j-i is a power of 2 (1,2,4, so on). Such a move costs him energy |Height[j]-Height[i]|, where Height[i] is the height of the ith building. Find the minimum energy using which he can reach building N?

Input:

First line contains N, number of buildings. Next line contains N space-separated integers, denoting the array Height.

Output:

Print a single integer, the answer to the above problem.

So, I thought of something like this:

int calc(int arr[], int beg, int end, )
{
    //int ans = INT_MIN;
    if (beg == end)
        return 0;
    else if (beg > end)
        return 0;
    else
    {
        for (int i = beg+1; i <= end; i++ ) // Iterate over all possible combinations
        {
            int foo = arr[i] - arr[beg]; // Check if power of two or not
            int k = log2(foo);
            int z = pow(2,k);
            if (z == foo) // Calculate the minimum value over multiple values
            {
                int temp = calc(arr,i,end);
                if (temp < ans)
                    temp = ans;
            }
        }
    }
}

The above is a question that I am trying to solve and here is the link: https://www.codechef.com/TCFS15P/problems/SPIDY2 However, the above recurrence is not exactly correct. Do I have to pass in the value of answer too in this?

Are you looking for the runtime (recurrance), or an algorithm? — The Brofessor, Aug 05 '15 at 04:52
No, I am looking for the recursive solution for this question. I tried developing it as above but I couldn't really. — John Lui, Aug 05 '15 at 04:53
Rather than using `log2()` and `pow()`, you can use `Integer.bitCount(foo) == 1)` as a test of whether `foo` is a power of 2. Also, don't you mean "recursive solution" rather than "exact recurrence"? Finally, what happened to the fourth argument to `calc()`, or is the trailing comma after `end` a typo? — Ted Hopp, Aug 05 '15 at 04:56
Read the problem statement more carefully. It says something should be a power of 2. Look at the code. Where is power of 2 checked? Is the right thing being checked? There is also this little issue of energy from different steps. It needs to be summed up. Where are you doing this? — n. m. could be an AI, Aug 05 '15 at 05:00
When you have finished calculating the total energy, you probably want to do something other than throwing away the result. — n. m. could be an AI, Aug 05 '15 at 05:05
So, I am thinking of doing something like `n & (n-1) == 0` as a check for testing if a number is power of 2 or not. But, then how do I exactly keep track of minimum value after adding in the height difference? — John Lui, Aug 05 '15 at 05:13

xashru · Answer 1 · 2015-08-07T08:22:56.347

2

We can reach nth building from any of (n-2^0),(n-2^1),(n-2^2)... buildings. So we need to process the buildings starting from 1. For each building i we calculate cost for getting there from any of earlier building j where i-j is power of 2 and take the minimum cost.

int calc(int arr[],int dp[],int n) {
    // n is the target building
    for(int i=1; i<=n; i++) dp[i]=LLONG_MAX;  //initialize to infinity
    dp[1]=0;  // no cost for starting building
    for(int i=2; i<=n; i++) {
        for(int j=1; i-j>=1; j*=2) {   
            dp[i]=min(dp[i], dp[i-j]+abs(arr[i]-arr[i-j]));
        }
    }
    return dp[n];
}

Time complexity is O(n*log(n)).

edited Aug 07 '15 at 08:22

answered Aug 06 '15 at 10:20

xashru

3,400
2
17
30

I have up voted your answer but still there is a slight bug in your program. You have not taken care of "j-i is a power of 2" requirement. In your code, j = 8 and i = 3 will lead to 5 as j-i value. – newbie_old Aug 09 '15 at 02:27

score 0 · Answer 2 · answered Aug 05 '15 at 05:20

First, you are doing the check for a power of 2 on the wrong quantity. The jumps have to be between buildings that are separated in index by a power of 2, not that differ in height (which is what you are checking).

Second, the recursion should be formulated in terms of the cost of the first jump and the cost of the remaining jumps (obtained by a recursive call). You are looking for the minimum cost over all legal first jumps. A first jump is legal if it is to a building that is at an index less than N and also a power of 2 in index away from the current start.

Something like this should work:

int calc(int arr[], int beg, int end)
{
    if (beg == end)
        return 0;
    else if (beg > end)
        throw an exception

    int minEnergy = INFINITY;
    for (int i = 1;        // start with a step of 1
         beg + i <= end;   // test if we'd go too far
         i <<= 1)          // increase step to next power of 2
    {
        int energy = abs(arr[beg + i] - arr[beg])  // energy of first jump
                   + calc(arr, beg + i, end);      // remaining jumps
        if (energy < minEnergy) {
            minEnergy = energy;
        }
    }
    return minEnergy;
}

The efficiency of this search can be greatly improved by passing the minimum energy obtained so far. Then if abs(arr[beg + i] - arr[beg]) is not less than that quantity, there's no need to do the recursive call, because whatever is found will never be smaller. (In fact, you can cut off the recursion if abs(arr[beg + i] - arr[beg]) + abs(arr[end] - arr[beg + i]) is not smaller than the best solution so far, because Spiderman will have to at least spend abs(arr[end] - arr[beg + i]) after getting to building beg + i.) Adding this improvement is left as an exercise. :)

Can't we make the for loop run like, `for (int i = beg; i <= end; i++)` and check `if (beg - i) is a power of two or not, and if is, we pass in the recursive calls?` — John Lui, Aug 05 '15 at 05:26
@JohnLui - But why would you bother doing that? My loop simply iterates over power-of-two steps and completely eliminates the generate-and-test costs that your approach would have. In other words, `(beg + i) - beg` is _always_ a power of two in my loop so there's no need to test if it is. — Ted Hopp, Aug 05 '15 at 05:29
I don't know why but using this function gives a wrong answer. In main, I am just calling this function and passing the appropriate values. — John Lui, Aug 05 '15 at 06:05
@JohnLui - Well, that code was off the top of my head. You might try debugging it with a simple case to see where it's going off the rails. :) — Ted Hopp, Aug 05 '15 at 06:33
The thing is, it works with simple small values. But with large input sizes, since its top down approach, it shows stack overflow. I guess I will have to do it using bottom-up approach. Any leads will help. :) — John Lui, Aug 05 '15 at 09:11
@JohnLui - Yes, the problem statement says that there may be as many as 200,000 buildings. That's just a bit too deep for a recursive solution. You might want to take a look at [this thread](http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) or do a general web search on the topic of converting to an iterative approach. — Ted Hopp, Aug 05 '15 at 14:44

How can I develop the exact recurrence for this?

2 Answers2