Databases
StackOverflow2013
Postsdbo
POHow is this DP solution approached?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow is this DP solution approached?
    primarykey
    data
    text
    <p>I have been trying to solve this TopCoder problem since a while now, and I'm not able to come up with a DP-based solution to this problem (given below). I also found a solution(also given below) by someone else to the problem, but I can't even understand it.</p> <p>Could anyone help me with the solution here? I don't understand what line of thought would lead to this solution? How do I go about establishing the recurrence relation in my mind? I have absolutely no clue how to approach this problem, or how the person who wrote that solution wrote it. </p> <p>PS: I'm aware TopCoder has editorials for problems, but this one's hasn't been released. I don't know why. </p> <p>Here's the <a href="http://community.topcoder.com/stat?c=problem_statement&amp;pm=11860&amp;rd=15091" rel="nofollow">problem</a></p> <blockquote> <p>Fox Ciel has lots of homework to do. The homework consists of some mutually independent tasks. Different tasks may take different amounts of time to complete. You are given a int[] workCost. For each i, the i-th task takes workCost[i] seconds to complete. She would like to attend a party and meet her friends, thus she wants to finish all tasks as quickly as possible. </p> <p>The main problem is that all foxes, including Ciel, really hate doing homework. Each fox is only willing to do one of the tasks. Luckily, Doraemon, a robotic cat from the 22nd century, gave Fox Ciel a split hammer: a magic gadget which can split any fox into two foxes. </p> <p>You are given an int splitCost. Using the split hammer on a fox is instantaneous. Once a hammer is used on a fox, the fox starts to split. After splitCost seconds she will turn into two foxes -- the original fox and another completely new fox. While a fox is splitting, it is not allowed to use the hammer on her again. </p> <p>The work on a task cannot be interrupted: once a fox starts working on a task, she must finish it. It is not allowed for multiple foxes to cooperate on the same task. A fox cannot work on a task while she is being split using the hammer. It is possible to split the same fox multiple times. It is possible to split a fox both before and after she solves one of the tasks. </p> <p>Compute and return the smallest amount of time in which the foxes can solve all the tasks.</p> </blockquote> <p>Here's the <a href="http://sk765.blogspot.in/2012/04/topcoder-open-2012-round-1b.html" rel="nofollow">solution</a>:</p> <pre><code>1: 2: const int maxN = 55; 3: int dp[maxN][maxN*2]; 4: int N; 5: int splitC; 6: vector&lt;int&gt; workC; 7: 8: int rec(int,int); 9: int FoxAndDoraemon::minTime(vector &lt;int&gt; workCost, int splitCost) { 10: 11: sort(workCost.begin(), workCost.end()); 12: N = workCost.size(); 13: splitC = splitCost; 14: workC = workCost; 15: memset(dp, -1, sizeof(dp)); 16: 17: return rec(N-1, 1); 18: } 19: 20: int rec(int jobs, int fox) 21: { 22: if(jobs == -1) return 0; 23: 24: int&amp; val = dp[jobs][fox]; 25: if(val != -1) return val; 26: val = 0; 27: 28: if( (jobs+1) &lt;= fox) val = max(workC[jobs] , rec(jobs-1, fox-1)); 29: else 30: { 31: //split fox 32: val = splitC + rec(jobs, fox + 1); 33: 34: if( !(fox == 1 &amp;&amp; jobs &gt; 0) ) 35: val = min(val, max(workC[jobs], rec(jobs-1, fox-1))); 36: } 37: return val; 38: } 39: </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USiCodez
    1. USProgramming Noob
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow is this DP solution approached?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow is this DP solution approached?
      1. USDerek Ledbetter
      1. VTFavorite
    3. VO
      singulars
      1. POHow is this DP solution approached?
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload