Recently De-shaw visited our campus and in coding round I am unable to solve this Problem.
Thanos is on his mission to destroy the universe. He comes across a new galaxy "Ravura". There are n planets lined up one after the other in Ravura. Thanos wants to destroy this galaxy, for which he will have to destroy each planet.
Thanos can destroy a planet Pi ( 1 <=i<=n ) by:
• Firing a bomb at Pi, but it incurs him a cost ci.
•If Pi-1 & Pi+1 have been destroyed , Thanos can destroy Pi (1 < i < n )with a snap of his fingers. This does not incur him any cost .
You are given a function destroy with 2 parameters. Return the minimum cost Thanos should incur to destroy all the planets in Ravura.
Parameter:
- A binary array p, where 'O' and '1' represent existent and destroyed planets respectively. (Seems Ronan has already done some part of the work. )
- An integer array c , where ci represents the cost of destroying a planet.
Input Format:
The locked code stub in the editor reads the following input from stdin:
First line contains the value n, the size of array p.
Next n lines contains the elements of the array p.
Next line contains the value n, the size of array c.
Next n lines contains the elements of the array c.
Constraints:
1<=n<=10^5
0<=p[i]<=1 where (1<=i<= n)
1<=c[i]<=10^9 where(1<=i<= n)
Output Format:
Return an integer from the function destroy.
Sample Input 1:
4
0
1
1
0
4
1
1
1
1
Sample Output 1:
2
Function to complete is
long destroy(vectorp, vector c){
}
why is cost 2, you can destroy one,take other for free right ?
Existing planets are denoted by 0, not 1.
Let us assume 1 means occupied, o means empty. Greedily take the minimum ci and delete it, if the element is alone(0's on either side) delete it for free.
Greedy might not work for this problem. Consider this case : ( I have assumed '1' denotes a planet that has NOT been destroyed ) p = [1 1 1 1] c = [4 1 1 4] Greedy Answer = 10 (indices 1,2,0) Actual Answer = 9 (indices 0,1,3)
Why? Because planets at end points have to be destroyed by incurring their costs. Even after explicitly handling this case we won't get the correct answer. Consider this : p = [0 1 1 1 1 1 1 1 1 0 0] c = [0 7 5 3 1 2 4 6 8 0 0] Greedy Answer = 21 (2,3,4,5,6,7) Actual Answer = 14 (2,4,5,7)
Dp can he used to solve this problem efficiently, the recursive relation comes out to be :
if(p[i]=='1') dp[i] = c[i] + min(dp[i-1],dp[i-2]) else dp[i] = 0 + min(dp[i-1],dp[i-2]
dp[i] denotes answer for segment[0..i]