Algorithm dynamic program

Question

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.

Where did the robots come from? Do you have any foundation to go on, like knowing what dynamic programming is? — wkl
– wkl, Commented Mar 28, 2012 at 16:31
yes, I have been trying to frantically learn it for the last 3 hours. I understand that it recursively makes the problem smaller until it reaches the base case, these are saved to help save memory and to stop working out the same problem twice. — user1261083
– user1261083, Commented Mar 28, 2012 at 16:34
If I answer the questions, do I get the gift card? Have you put any effort into this? — Blender
– Blender, Commented Mar 28, 2012 at 16:34
In order to receive help, you need to show what you have tried before and where you are stuck. If you have no clue where to even start, go and start reading up on recursion and dynamic programming — Attila
– Attila, Commented Mar 28, 2012 at 16:35
@blender. you are more then welcome to it, but it seems like a really hard question for only 25 euro's. — user1261083
– user1261083, Commented Mar 28, 2012 at 16:36

IVlad · Accepted Answer · 2012-03-28 17:35:57Z

2

(a) 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], (2-0)^2), S(1) + min(x[2], (2 - 1)^2)} =
     = max{0 + 4, 1 + 1} 
     = 4
S(3) = max{S(0) + min(x[3], (3 - 0)^2), S(1) + min(x[3], (3-1)^2), S(2) + min(x[3], (3-2)^2)}
     = max{0 + 9, 1 + 4, 4 + 1}
     = 9
S(4) = max{S(0) + min(x[4], (4 - 0)^2), ..., S[3] + min(x[4], (4-3)^2)}
     = max{0 + 1, ..., 9 + 1}
     = 10

(b) 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).

answered Mar 28, 2012 at 17:35

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Algorithm dynamic program

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related