triggered_'s blog

By triggered_, history, 7 weeks ago, In English

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:

  1. A binary array p, where 'O' and '1' represent existent and destroyed planets respectively. (Seems Ronan has already done some part of the work. )
  2. 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){

}

 
 
 
 
  • Vote: I like it
  • -23
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by triggered_ (previous revision, new revision, compare).

»
7 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

1<=n<=105? Do you mean n<=10^5 or n<=105. Regardless, firstly you can split each group of planets and solve for it independently and for each groups of planets, I think the idea of the solution is to destroy a configuration of planets such that the distance between consecutive planets is atmost 2, and for that you can do a dp.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

why is cost 2, you can destroy one,take other for free right ?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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]