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.
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], 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 and dp[n] is infinite.
- For the sake of simplicity, let dp[i] and dp[i] 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 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] = 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] 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] + 2a + b) , (dp[i - 1] + 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] + 2a + 2b), (dp[i - 1] + a + 2b)) i.e coming from height 1 or height 2 respectively.
Finally, our answer is dp[n].
O(n) time per test case
Hope you liked this editorial and any suggestion on how to make it better or any approach of yours is openly welcome.