[OT] Retreating from Iraq

[Sean Kelly]

Andrei Alexandrescu wrote:
> 
> Nope, not optimal. Please reread the spec.

Hm... based on the requirements, the options available are very limited. 
  Each person must call his subordinates iteratively, so the time 
required for all members of a subtree to be notified is a function of 
the size of that subtree.

I'm sure there's a great way to summarize the time taken with this 
method using graph theory (this smells a lot like trying to optimize a 
breadth-first search), but in essence the time taken to notify all 
members of a subtree will be proportional to the number of edges to be 
traversed to reach the most distant member, with the number of siblings 
contacted prior to any member included in the distance.  For example:

a: b,c
b: d
c: e,f,g
d: h
e:
f:
g:
h: i
i:

The following edges must be evaluated to reach g:

a->b, a->c, c->e, c->f, c->g

So assuming:

class Person
{
     Peson[] subs;
     size_t calls();
}

To construct an optimal calling strategy,  subs must be ordered as a max 
heap on calls(), where calls() represents the number of phone calls 
required before the most distant subordinate is contacted.  This should 
be relatively easy to construct from the bottom up.


Sean