77035 # Algorithm dynamic program

I was reading a computer science magazine today from Ireland and it has a competition for answering this question. could anyone help me to solve it.

The problem.

Given x1….., xn, determine the times that the EMP should be activated to destroy the maximum number of aliens.

Example. Suppose n = 4 and x1…x4 = 1, 10, 10, 1. Then the best solution would be to activate the EMP in the 3rd and 4th minutes. In the 3rd minute, it destroys min(10,3^2) = 9 aliens. Then in the 4th minute, it destroys min(1,1^2) = 1 alien. This gives a total of 10 aliens.

2 Questions

(a) Let S(j) denote the maximum total number of aliens destroyed for the subproblem consisting of the aliens arriving in the first j minutes only. Give a recursive formula for S(j). Also, write down the base case. (Hint: for S(j), you always activate the EMP at the j-th minute. Suppose the previous activation happens at the i-th minute. Try all possibilities of i and take the maximum.)

(b) Give a dynamic programming algorithm for this problem. Analyze the time and space complexity of the algorithm.

Key points:- A swarm of aliens arrive over the course of n minutes. In the i-th minute, xi aliens arrive. Based on remote sensing data, you know this sequence x1… xn in advance.

You have at your disposal an electromagnetic pulse (EMP), which can destroy some of the aliens. The EMP's power depends on how long it has been allowed to charge up. To make this precise, if j minutes have passed since the EMP was last used, it is capable of destroying j2 aliens.

The EMP only destroys aliens arriving in the exact minute that it is activated. In other words, it does not destroy any aliens arriving earlier or later.

Therefore, if it is used in the k-th minute, and it has been j minutes since it was previously used, then it destroys min(xk, j2) aliens (i.e., whichever xk or j2 is smaller).

After each use the EMP will be completely drained. We also assume the EMP starts off(at the 0-th minute) as completely drained.

<strong>(a)</strong> The hint gives it away really. `S(0) = 0` obviously, and `S(1) = 1`. We have that:
`S(j) = max{S(i) + min(x[j], (j - i)^2) : 0 <= i < j}`. This really just does what the hint says. Here's how it will run on your example:
```1 10 10 1 S(0) = 0 S(1) = 1 S(2) = max{S(0) + min(x, (2-0)^2), S(1) + min(x, (2 - 1)^2)} = = max{0 + 4, 1 + 1} = 4 S(3) = max{S(0) + min(x, (3 - 0)^2), S(1) + min(x, (3-1)^2), S(2) + min(x, (3-2)^2)} = max{0 + 9, 1 + 4, 4 + 1} = 9 S(4) = max{S(0) + min(x, (4 - 0)^2), ..., S + min(x, (4-3)^2)} = max{0 + 1, ..., 9 + 1} = 10 ```
<strong>(b)</strong> I already solved it above. Just hold `S` as an array. Since the computation of each `S(i)` requires iteration of all `j < i`, each `S(i)` takes `O(n)` time, so the entire algorithm is `O(n^2)`.