De-Shaw Intern Hiring Test Problem

Recently De-shaw visited our campus for intern hiring and I am unable to solve this problem.

  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<=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(vector p, vector c){

}

2 Likes

Consider the zeros between the two 1, we need to destroy them. Let’s suppose we fire the bomb at positions i_1, i_2,..,i_k. The other bombs(if left any) would be destroyed using 2nd operation. The condition is: |i_j - i_{j-1}| \leq 1 , because if there are more than 2 zeros left between any 2 ones, then we need to destroy some more bombs. Further, You need to minimize: \sum\limits_{j = 1}^{k} C_{i_j} . To minimize this sum, we would use a trick, consider the positions on which we are going to apply 2^{nd} operation. Clearly they are not adjacent. Therefore if we can find the sum of maximum non-adjacent elements in the subarray between two ones, we can minimize that function by subtracting this maximum value from the sum of elements of this subarray. To maximize sum of non-adjacent elements in the subarray:

Overall Complexity : O(n)

1 Like

Thanks a Lot Man for Help.
It works like charm.