CMI2018-B-6

Question

You are playing an old-style video game in which you have to shoot down alien spaceships as they fly across the screen from left to right. Each spaceship flies across the screen at a specified height. You have an antiaircraft gun set to shoot down all spaceships at a certain height. Spaceships fly one at a time, so if your gun is set to fire at the correct height, it will shoot down the spaceship currently flying across the screen.

You can set the initial height at which the gun fires. As the game progresses, you can reset the height, but only to a lower value. You are given in advance the height at which each spaceship flies. There are $N$ spaceship numbered $1,2,\cdots, N$ in the order in which they fly across the screen. For $1\leq i\leq N,\:h[i]$ denotes the height at which spaceship $i$ flies.

• A. Let $V[i]$ denotes the maximum number of spaceships from $i,i+1.\cdots, N$ that you can shoot down with a single gun. Write a recurrence for $V[i]$ and describe a strategy to compute  $V[i]$ using dynamic programming. What is the space and time complexity of your solution?
• B. Describe an algorithm to compute the minimum number of guns required to shoot down all the space ships. Each gun can be initialized separately to a firing height and each gun can be separately reset to a lower value. 

Answer 1

As we can only reset the height of the gun to lower point, so I think from the given h[i] array, we need to find out the longest decreasing subsequence and store it to V[i]. 

When we have calculated the V[i], it means this spaceship sequence we can shoot down with a single gun at different time interval.

You can refer to the code at this link:- http://www.geekviewpoint.com/java/dynamic_programming/lds

Time complexity will be O(n^2) and space complexity will be O(n).

Answer 2