A staircase can be represented by a sequence of monotonically increasing numbers

Question

A staircase can be represented by a sequence of monotonically increasing numbers, which represent the heights of the steps. For example, consider the sequence {1, 3, 3, 9, 10}. This means the first step is of height 1. Next, we have two 3's; this means we have a wider step (of width 2) at height 3. Next, the 9 means we have a jump to the next step at height 9, and so on. Suppose we wish to grow plants on the staircase. However, we need the width of every step to be of width at least 2. In our example, the steps at height 1, 9 and 10 do not satisfy this condition. We are allowed to increase the heights of the steps. For example, we can increase the 1 by 2 and increase the 9 by 1 to obtain the valid sequence {3, 3, 3, 10, 10). The cost is 2 + 1 = 3. Of course, we can also increase the first four numbers to obtain {10, 10, 10, 10, 10}, but the cost is higher (9 + 7 + 7 + 1 = 14). In general, suppose you are given n integers a_1 lessthanorequalto a_2 lessthanorequalto ... lessthanorequalto a_n, which represent a staircase in the manner described above. Moreover, suppose now we want to grow larger plants, and the requirement is that the width of every step has to be at least k. (We must have k lessthanorequalto n, otherwise this is impossible.) The goal is to find the minimum cost of increasing the numbers to satisfy this condition. (a) Suppose k lessthanorequalto n lessthanorequalto 2k - 1. What is the minimum cost in this case? (b) Give an algorithm that computes the minimum cost to obtain a valid sequence. What is the running time of your algorithm?

Explanation / Answer

a). Since we have been given than the range of n will be between k and 2k-1. Hence, there is only one step possible at a time where we can grow plants.
   Because n<2k.
   Now coming to the problem, we have the liberty to increase the heights to make a particular step level up with some other step. In order to find the
   minimum cost required to level up the steps to make it of width k, the algorithm will be as follows:
   1. We will use the sliding window technique in which we will take the first k steps from the input array. See how much cost it takes to level up the
   k steps upto the step with maximum height. Save the cost in a variable let's say 'result'.
   2. Start removing steps one by one from the left, update the max_height in the window and update the cost of the current steps.
   3. Start adding steps one by one from the right and update the new cost as the height of the new step. Thereby check if the current cost is less than
   the saved 'result'. If yes then update the 'result'.
     
void find_minimum_cost(int[] input, int n, int k)
{
   int cost, i, index = 0;
   int result = INT_MAX;
   int max_height = 0;
   int local_height=0;
   int height_array[n-k+1];
   height_array[index]=0;
   /* update the max_height for every k window and save it in an array.
   height_array[0] represents the max_height in first k steps (0 to k), height_array[1]
   represents the max_height in the next k steps (1 to k+1) and so on..*/
   for(int j=1; j<n; j++)
   {
       if(j<=k && input[j]>input[height_array[0]])
           height_array[index]=j;
       else if(j-height_array[index]>k)
       {
           index++;
           height_array[index]=j;
       }
       else if(j-height_array[index]<k and input[j]>input[height_array[index]])
       {
           index++;
           height_array[index]=j;          
       }
   }
   index=0;
   max_height=input[height_array[index]];
   for(i=0; i<k; i++)
       cost=cost+(max_height-input[i]); //update the cost for first k steps
   if(result>cost)
       result=cost; // update the final result
   /* start the sliding window technique */
   while(i<n)
   {
       index++;
       max_height=input[height_array[index]];
       if(max_height>input[i-k-1]) // max_height is still in the current window then we only need to update the first and the last step's cost
       {
       cost=cost-input[i-k-1];
       cost=cost+input[i];  
       if(result>cost)
           result=cost;      
       }
       /*max_height gets removed from the current window hence we need to recalculate the whole cost for the window */
       else if(max_height==input[i-k-1] && height_array[index]==i-k-1)
       {
           cost=0;
           for(int t=i; t<i+k; t++)
               cost=cost+(max_height-input[t]);
           if(result>cost)
               result=cost;
       }
   }
   return result; //finally return the result variable
}

b) In the worst case when all the heights are given in descending order it will run in O(n^2) time.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.