Databases
StackOverflow2013
Postsdbo
POWhy does this code work for this TopCoder prob?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy does this code work for this TopCoder prob?
    text
    copied!<p>I've been trying to think since HOURS about this TopCoder problem and couldn't come with a perfectly working solution and found the one given below that is insanely beautifully used!</p> <p>I'm trying to figure how this solution works for the given probem? And how could I have originally thought of it? After reading the solution I figured it's a variant of Huffman coding but that's as far as I could get. I'm really enthralled and would like to know what line of thought could lead to this solution..</p> <p>Here's the problem: <a href="http://community.topcoder.com/stat?c=problem_statement&amp;pm=11860&amp;rd=15091">http://community.topcoder.com/stat?c=problem_statement&amp;pm=11860&amp;rd=15091</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>And here's the solution I found at this <a href="http://community.topcoder.com/stat?c=problem_solution&amp;rm=312431&amp;rd=15091&amp;pm=11860&amp;cr=23056191">link</a></p> <pre><code>import java.util.*; public class FoxAndDoraemon { public int minTime(int[] workCost, int splitCost) { PriorityQueue&lt;Integer&gt; pq = new PriorityQueue&lt;Integer&gt;(); for(int i : workCost) pq.offer(i); while(pq.size()&gt;=2) { int i = pq.poll(); int j = pq.poll(); pq.offer(Math.max(i, j) + splitCost); } return pq.poll(); } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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