Why does this code work for this TopCoder prob?

Question

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!

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

Here's the problem: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091

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.

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.

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.

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.

Compute and return the smallest amount of time in which the foxes can solve all the tasks.

And here's the solution I found at this link

import java.util.*; 

public class FoxAndDoraemon { 
  public int minTime(int[] workCost, int splitCost) { 
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 

    for(int i : workCost) pq.offer(i); 

    while(pq.size()>=2) { 
      int i = pq.poll(); 
      int j = pq.poll(); 
      pq.offer(Math.max(i, j) + splitCost); 
    } 
    return pq.poll(); 

  } 
}

Answer 1

First of all you do realize the reasoning behind `max(i, j) + splitCost'. Don't you? Basically, if you have one fox, you split it into two and perform each task independently. Let us call this process "merging".

Now assume we have three jobs a,b and c such that a>b>c. You can either do merge(merge(a,b),c) or merge(merge(a,c),b) or merge(merge(b,c),a). Do the math and you can prove that merge(merge(b,c),a) is least among these three.

You can now use induction to prove that this solution is valid for any number of jobs (not just 3).

Answer 2

It's building a tree from the ground up.

The algorithm uses one basic fact to work: If you remove the two smallest elements, the cost of computing the smallest element is always less than the cost of the next smallest plus a split. (See ElKamina's post for a much more thorough proof for this).

So if you only had two elements in your tree (say 4 and 2) and your split cost was 4, the lowest amount of time is always going to be 8 (the next to smallest element plus the cost of splitting.

So, to build our tree: let's say we got the workCost [1,3,4,5,7,8,9,10], and our splitCost is 3.

So, we look at the two smallest elements: 1,3. The 'cost' of computing these is at minimum 6 (the largest number plus the cost of a split. By then reinserting 6 into the queue, you're essentially adding the subtree:

  6
1   3

Where the 'height'/'cost' is 6 total. By repeating this process, you will build a tree using the smallest subelements you can (either an existing subtree, or a new unfinished homework).

The solution will eventually look like this: (Where S(X) is the cost of splitting plus solving everything below it)

                  S(17)
            S(13)       S(14)
       S(10)     9   10      S(11)
  S(6)      7            S(8)     8
1     3                 4    5

If you trace backwards up this tree, it's easy to see how the formula solved it: the cost of 1 and 3 is S(6), 4 and 5 is S(8), then S(6) and 7 is S(10), 8 and S(8) is S(11), etc.