PROBLEM LINKS:
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic-programming
PROBLEM:
Given a binary array(i.e of zeroes and ones), we have to fix a gas pipeline in such a way that when we encounter a one in the array, its height is 2. One unit of pipeline costs a units of money and one unit of the pillar on which the pipeline stands costs b units of money. We need to find the minimum money spent. The first and the last elements of the array are 0.
EXPLANATION:
After observing, we get to know that the directions in which the pipeline can go are as follows:
- Straight, along height of 1.
- Straight, along height of 2.
- From height 1 to height 2.
- From height 2 to height 1.
Now lets determine the cost for building the pipeline in these four ways:
- Straight, along height of 1. This will cost an extra unit of pipeline and pillar. So we will add a and b to our answer.
- Straight, along height of 2. This will cost an extra unit of pipeline and 2 extra units of pillars. So we will add a and 2b to our answer.
- From height 1 to height 2. This will cost 2 extra units of pipeline and pillars So we will add 2a and 2b to our answer.
- From height 2 to height 1. This will cost 2 extra units of pipeline and an extra unit of pillar. So we will add 2a and b to our answer.
If you couldn’t understand the above explanation, here is an image for your explanation.
Now, finally coming to dp.
We will build a 2d array of dp[n + 1][2], where the 2nd dimension is added for the height of the pipeline.
- As we can neither start, nor end with a height of 2, dp[0][1] and dp[n][1] is infinite.
- For the sake of simplicity, let dp[i][0] and dp[i][1] correspond to the point after the ith element of the binary array as we have the points in between two consecutive elements(1 indexed). Image for clarification.
- The base case is: dp[0][0] which needs one unit of pillar(the starting of the pipeline)
- Now lets look at the recursive part.
a) If arr[i] = 1, then dp[i][0] = INF, because we can’t have a pipeline of height 1 there. Same thing goes when arr[i + 1] is 1, because we need a horizontal pipe of unit 1 for rising it to height 2.
b) If arr[i - 1] = 1, the dp[i][0] can only come from height 1. Thus we will have to descend the pipeline from height 2 to height 1. Which will cost 2a and b extra money
c) Else, it can come from height 1 or height 2. Thus, it will be min ((dp[i - 1][1] + 2a + b) , (dp[i - 1][0] + a + b)) i.e, coming from height 2 or height 1 respectively.
d) For height of 2, it can come from height 1 or height 2. Thus, it will be min((dp[i - 1][1] + 2a + 2b), (dp[i - 1][0] + a + 2b)) i.e coming from height 1 or height 2 respectively.
Finally, our answer is dp[n][0].
TIME COMPLEXITY:
O(n) time per test case
SOLUTION:
My solution
Hope you liked this editorial and any suggestion on how to make it better or any approach of yours is openly welcome.