De-Shaw Internship Test Question

Правка en5, от triggered_, 2020-12-03 12:22:32

Recently De-shaw visited our campus and in coding round I am unable to solve this question.

  1. Destruction Game 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<=105

0<=p[i]<=1 where (1<=i<= n)

1<=c[i]<=109 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){

}

Теги dp, internship 2021, de shaw

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский triggered_ 2020-12-03 15:06:41 2
en9 Английский triggered_ 2020-12-03 12:28:23 13 Tiny change: 'olve this question.\n\n\nTha' -> 'olve this Problem.\n\n\nTha'
en8 Английский triggered_ 2020-12-03 12:27:20 10
en7 Английский triggered_ 2020-12-03 12:26:03 30 Tiny change: '1 \n\n1 \n1 \n\nSa' -> '1 \n\n1 \n\n1 \n\nSa'
en6 Английский triggered_ 2020-12-03 12:23:50 4
en5 Английский triggered_ 2020-12-03 12:22:32 38
en4 Английский triggered_ 2020-12-03 12:21:06 6
en3 Английский triggered_ 2020-12-03 12:19:13 4
en2 Английский triggered_ 2020-12-03 12:18:30 4
en1 Английский triggered_ 2020-12-03 12:17:53 1666 Initial revision (published)