Solution to "Divided Tree Processing"

View Problem: Divided Tree Processing

Initially, let us assume that the task can be completed in 0 time. This would mean that each parent assigns sub-tasks to its children at the same time which is T = 0. We will now delay the sub-task distribution only where it will be required, thus minimizing the time to complete the task.

Let time_received[i] denote the time at which node i received its task. Let time_completed[i] denote the time at which node i completed its task. If node i has children, let child[i][0] and child[i][1] denote the indices of its children.

Let us say that both the children complete their tasks at the same time. This case has to be avoided, so we simply delay the giving away of sub-task for one of the children by 1 time unit. This will work due to our initial assumption that all parents distribute the sub-tasks to their children at the same time. We then apply this condition recursively (assume initially for all i, time_received[i] = time_completed[i] = 0):

calculate(i)
{
    if(!hasChildren(i))
    {
        time_received[i] = 0;
        time_completed[i] = 0;
    }
    else
    {
        calculate(child[i][0]);
        calculate(child[i][1]);

        if(time_completed[child[i][0]] == time_completed[child[i][1]])
        {
            /*
             Increment by 1 the time_received[i] and time_completed[i] for all i 
             such that node i belongs to the sub-tree rooted at node child[i][1].
            */

            time_completed[i] = time_completed[child[i][0]] + 1;
        }
        else
        {
            time_completed[i] = max(time_completed[child[i][0]], time_completed[child[i][1]]); 
        }
    }
}

calculate(1) fills time_received[i] and time_completed[i] for all i. time_completed[1] gives us the minimum time taken by the system to complete the entire task.

The above algorithm can be optimized. Instead of incrementing the values of time_completed[i] and time_received[i] for all i which belong to the sub-tree rooted at node child[i][1], we can store separately for which sub-tree the increment has to be performed. In the end, these stored values can be added in a cumulative fashion by following a top-down approach.