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.

Answer1:

<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], (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

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

Recommend

  • Comparing Groups in data.table Columns
  • ASP.NET MVC 2 - ViewData empty after POST
  • How can an app determine if its being launched from a terminated state due to Voip Push?
  • How to free a TObject member in a TInterfacedObject
  • c/linux - ftruncate and POSIX Shared Memory Segments
  • Rails 4.1 Nested Attributes and Fields For Getting Unpermitted Parameters and Not Saving
  • Observable to batch like Lmax Disruptor
  • watch request to new topic pauses push notifications to existing topic
  • strtotime() converts a non existing date to another date
  • Customized tooltip for C3JS
  • How to get scaled bitmap with respect to screen size with out getting Out of memory exception
  • Ruby on Rails prevent Turbolinks from hijacking AJAX action
  • java Process stop entire process tree
  • golang reflect get closure function pointer
  • No “Destroy” confirmation from Browser running Ruby/Rails app on Heroku
  • Closing Http response stream in NodeJS before it ends
  • VisualVM unable to connect remote tomcat in docker with RMI
  • Is it a bad practice to rely on local objects get destructed in the reverse order of construction in
  • Sum, Avg, Max, Min, Count of NULL values
  • Android v2.2-2.3.5: WebView : loadDataWithBaseURL : will only load page once
  • WebView memory leak
  • Does derived class' member functions inherit virtualness from base class?
  • Binary search using iterators, why do we use “(end - begin)/2”? [duplicate]
  • Confusing prototype behavior in JavaScript
  • Getting webGL error in autodesk viewer
  • Is there a way to clear some session data from ALL sessions?
  • PHPUnit: Expected status code 200 but received 419 with Laravel
  • https in htaccess and order of rules (using Expression Engine)
  • Recommended way to remove events on destroy with jQuery UI Widget Factory
  • Submission of new app with iAds
  • Losing my session variables
  • Divide a $1 by 3 and adjusting 1 cent
  • ConnectivityManager.CONNECTIVITY_ACTION deprecated
  • SQL: Getting the physical size of a subset of a table
  • pip in virtualenv gets ConnectTimeoutError
  • Sequential (transactional) API calls in angular 4 with state management
  • Marklogic : Query response time is very high
  • Javascript Callbacks with Object constructor
  • Matrix multiplication with MKL
  • File upload with ng-file-upload throwing error