www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [OT] Retreating from Iraq AT THE SAME TIME

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Let's reconsider the problem of retreating from Iraq, with a twist.
Grace to new technology, teleconferencing is now possible. All direct
subordinates of any officer can be called SIMULTANEOUSLY. So there is no
more need for one officer to call each subordinate in sequence; he or 
she will call them all at once. Cool!

However, now the demands also increased. Your task, should you yadda
yadda, is to devise a schedule for teleconferenced such that EVERY rank
and file soldier finds the news at EXACTLY the same time. That means you
must insert some delays in the system. However, you should insert as few
delays as possible, and also to ensure there is minimal global delay
from the moment the President picks up the phone to the moment soldiers
get the news.

Be warned: this is quite a different problem than the previous one in
spite of the similarities. You may want to start from scratch instead of
adapting an algorithm suitable for the previous problem.


Good luck!

Andrei
Oct 15 2008
next sibling parent reply Benji Smith <dlanguage benjismith.net> writes:
Andrei Alexandrescu wrote:
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or 
 she will call them all at once. Cool!
 
 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.
 
 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.
 
 
 Good luck!
 
 Andrei

Hmmmmmm. Does each officer have the *option* of calling subordinates at different times? Can an officer have a conference call with all of his subordinates who have subordinates of their own, delaying a call with the leaf-node privates until later? If not, I can't imagine there's any generalizable solution... --benji
Oct 15 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Benji Smith wrote:
 Andrei Alexandrescu wrote:
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or 
 she will call them all at once. Cool!

 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.

 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.


 Good luck!

 Andrei

Hmmmmmm. Does each officer have the *option* of calling subordinates at different times? Can an officer have a conference call with all of his subordinates who have subordinates of their own, delaying a call with the leaf-node privates until later? If not, I can't imagine there's any generalizable solution...

Each officer can only wait for a specified time before calling all direct subordinates. You need to figure out how long each officer waits. Andrei
Oct 15 2008
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Andrei Alexandrescu wrote:
 Benji Smith wrote:
 Andrei Alexandrescu wrote:
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or 
 she will call them all at once. Cool!

 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.

 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.


 Good luck!

 Andrei

Hmmmmmm. Does each officer have the *option* of calling subordinates at different times? Can an officer have a conference call with all of his subordinates who have subordinates of their own, delaying a call with the leaf-node privates until later? If not, I can't imagine there's any generalizable solution...

Each officer can only wait for a specified time before calling all direct subordinates. You need to figure out how long each officer waits.

Rats, I'm wrong (Sean just explained me over Skype). Yes, an officer can insert delays in calling certain subordinates. Andrei
Oct 15 2008
prev sibling next sibling parent reply Gregor Richards <Richards codu.org> writes:
You want to destroy all life on Earth. However, you don't want people 
panicking as this could alter the result, so you want all humans to die 
at the same instant. To do this, you're creating nano-robots. A single 
nano-robot cannot control a persons mind: Seven are required (three in 
each half of the brain and one in the brain stem). Nano-robots can 
harvest material from their host to build new nano-robots, but the host 
will die after approximately twenty nano-robots-worth of material has 
been harvested (they require particular rare particles that can only be 
harvested from the heart and lungs). Nano-robots may communicate with 
one-another via broadcast, but the range is limited to 1 mile. 
Nano-robots do not have unique identification globally, but do have 
unique identification within a body (that is, nano-robots in the same 
body can distinguish each other, but broadcast messages from a 
nano-robot in one human cannot implicitly be distinguished from 
broadcasts from another). These broadcasts travel at the speed of light 
(seeing as that they are light). Nano-robots harvest energy from their 
host, and as such can survive indefinitely. A nano-robot in a dead host 
survives long enough that this variable is not relevant for this problem.

Robots can only be spread by direct physical contact from an infected 
host to an uninfected one, and the process of transferring one 
nano-robot destroys two nano-robots (that is, the infected host loses 
three robots in the process but the new host only gains one).

Devise an algorithm for these nano-robots that will destroy all human 
life on Earth in a minimum amount of time, but with which all humans 
will be destroyed within five minutes of each other. That is, minimize 
the time from deploying the first nano-robot to the initial human life 
being exterminated, and minimize the time from the initial human life 
being exterminated to all human life being exterminated. You may assume 
a maximum of twelve degrees of separation between average industrialized 
people and that even the most remote tribe is connected by at least one 
human to the industrialized world.

Bonus: How would you change this algorithm if you wanted to destroy all 
animal life? All life? How would you change it if astronauts were 
considered?

  - Gregor Richards
Oct 15 2008
parent reply John Reimer <terminal.node gmail.com> writes:
Hello Gregor,

 You want to destroy all life on Earth. However, you don't want people
 panicking as this could alter the result, so you want all humans to
 die at the same instant. To do this, you're creating nano-robots. A
 single nano-robot cannot control a persons mind: Seven are required
 (three in each half of the brain and one in the brain stem).
 Nano-robots can harvest material from their host to build new
 nano-robots, but the host will die after approximately twenty
 nano-robots-worth of material has been harvested (they require
 particular rare particles that can only be harvested from the heart
 and lungs). Nano-robots may communicate with one-another via
 broadcast, but the range is limited to 1 mile. Nano-robots do not have
 unique identification globally, but do have unique identification
 within a body (that is, nano-robots in the same body can distinguish
 each other, but broadcast messages from a nano-robot in one human
 cannot implicitly be distinguished from broadcasts from another).
 These broadcasts travel at the speed of light (seeing as that they are
 light). Nano-robots harvest energy from their host, and as such can
 survive indefinitely. A nano-robot in a dead host survives long enough
 that this variable is not relevant for this problem.
 
 Robots can only be spread by direct physical contact from an infected
 host to an uninfected one, and the process of transferring one
 nano-robot destroys two nano-robots (that is, the infected host loses
 three robots in the process but the new host only gains one).
 
 Devise an algorithm for these nano-robots that will destroy all human
 life on Earth in a minimum amount of time, but with which all humans
 will be destroyed within five minutes of each other. That is, minimize
 the time from deploying the first nano-robot to the initial human life
 being exterminated, and minimize the time from the initial human life
 being exterminated to all human life being exterminated. You may
 assume a maximum of twelve degrees of separation between average
 industrialized people and that even the most remote tribe is connected
 by at least one human to the industrialized world.
 
 Bonus: How would you change this algorithm if you wanted to destroy
 all animal life? All life? How would you change it if astronauts were
 considered?
 
 - Gregor Richards
 

Ok, Gregor. I'll bite. What's your fascination with this problem? Are you trying to make a point about something? If "yes", you may as well be direct about it. If "no", then why the thread hijacking? Come on... help me out... I'm a little slow sometimes. :) -JJR
Oct 15 2008
parent reply Gregor Richards <Richards codu.org> writes:
John Reimer wrote:
 Hello Gregor,
 
 You want to destroy all life on Earth. However, you don't want people
 panicking as this could alter the result, so you want all humans to
 die at the same instant. To do this, you're creating nano-robots. A
 single nano-robot cannot control a persons mind: Seven are required
 (three in each half of the brain and one in the brain stem).
 Nano-robots can harvest material from their host to build new
 nano-robots, but the host will die after approximately twenty
 nano-robots-worth of material has been harvested (they require
 particular rare particles that can only be harvested from the heart
 and lungs). Nano-robots may communicate with one-another via
 broadcast, but the range is limited to 1 mile. Nano-robots do not have
 unique identification globally, but do have unique identification
 within a body (that is, nano-robots in the same body can distinguish
 each other, but broadcast messages from a nano-robot in one human
 cannot implicitly be distinguished from broadcasts from another).
 These broadcasts travel at the speed of light (seeing as that they are
 light). Nano-robots harvest energy from their host, and as such can
 survive indefinitely. A nano-robot in a dead host survives long enough
 that this variable is not relevant for this problem.

 Robots can only be spread by direct physical contact from an infected
 host to an uninfected one, and the process of transferring one
 nano-robot destroys two nano-robots (that is, the infected host loses
 three robots in the process but the new host only gains one).

 Devise an algorithm for these nano-robots that will destroy all human
 life on Earth in a minimum amount of time, but with which all humans
 will be destroyed within five minutes of each other. That is, minimize
 the time from deploying the first nano-robot to the initial human life
 being exterminated, and minimize the time from the initial human life
 being exterminated to all human life being exterminated. You may
 assume a maximum of twelve degrees of separation between average
 industrialized people and that even the most remote tribe is connected
 by at least one human to the industrialized world.

 Bonus: How would you change this algorithm if you wanted to destroy
 all animal life? All life? How would you change it if astronauts were
 considered?

 - Gregor Richards

Ok, Gregor. I'll bite. What's your fascination with this problem? Are you trying to make a point about something? If "yes", you may as well be direct about it. If "no", then why the thread hijacking? Come on... help me out... I'm a little slow sometimes. :) -JJR

Thread hijacking? Seriously? This isn't a forum, there are totally disconnected subthreads within any thread. This is what we call a "joke". On the one hand it's a parody of the always-annoying real-life-algorithm thread, on the other hand it's a parody of the needlessly-loaded choice of settings for the oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This problem could be formalized as a simple tree-based message-passing communication problem, but instead we've gone political. Well, so long as war is involved, let's step it up and destroy everything. Yeeee haw. - Gregor Richards
Oct 15 2008
next sibling parent John Reimer <terminal.node gmail.com> writes:
Hello Gregor,

 John Reimer wrote:
 
 Hello Gregor,
 
 You want to destroy all life on Earth. However, you don't want
 people panicking as this could alter the result, so you want all
 humans to die at the same instant. To do this, you're creating
 nano-robots. A single nano-robot cannot control a persons mind:
 Seven are required (three in each half of the brain and one in the
 brain stem). Nano-robots can harvest material from their host to
 build new nano-robots, but the host will die after approximately
 twenty nano-robots-worth of material has been harvested (they
 require particular rare particles that can only be harvested from
 the heart and lungs). Nano-robots may communicate with one-another
 via broadcast, but the range is limited to 1 mile. Nano-robots do
 not have unique identification globally, but do have unique
 identification within a body (that is, nano-robots in the same body
 can distinguish each other, but broadcast messages from a nano-robot
 in one human cannot implicitly be distinguished from broadcasts from
 another). These broadcasts travel at the speed of light (seeing as
 that they are light). Nano-robots harvest energy from their host,
 and as such can survive indefinitely. A nano-robot in a dead host
 survives long enough that this variable is not relevant for this
 problem.
 
 Robots can only be spread by direct physical contact from an
 infected host to an uninfected one, and the process of transferring
 one nano-robot destroys two nano-robots (that is, the infected host
 loses three robots in the process but the new host only gains one).
 
 Devise an algorithm for these nano-robots that will destroy all
 human life on Earth in a minimum amount of time, but with which all
 humans will be destroyed within five minutes of each other. That is,
 minimize the time from deploying the first nano-robot to the initial
 human life being exterminated, and minimize the time from the
 initial human life being exterminated to all human life being
 exterminated. You may assume a maximum of twelve degrees of
 separation between average industrialized people and that even the
 most remote tribe is connected by at least one human to the
 industrialized world.
 
 Bonus: How would you change this algorithm if you wanted to destroy
 all animal life? All life? How would you change it if astronauts
 were considered?
 
 - Gregor Richards
 

Are you trying to make a point about something? If "yes", you may as well be direct about it. If "no", then why the thread hijacking? Come on... help me out... I'm a little slow sometimes. :) -JJR

disconnected subthreads within any thread.

Or whatever... thread "detracting" perhaps is a better term.
 This is what we call a "joke". On the one hand it's a parody of the
 always-annoying real-life-algorithm thread, on the other hand it's a
 parody of the needlessly-loaded choice of settings for the
 oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This
 problem could be formalized as a simple tree-based message-passing
 communication problem, but instead we've gone political. Well, so long
 as war is involved, let's step it up and destroy everything. Yeeee
 haw.
 
 - Gregor Richards
 

Ok, that's better. Thanks for clarifying. Actually, I didn't find it near as annoying as you did, but I do agree that it was getting a little too close to a political tune on something that is very likely a touchy subject... good call. -JJR
Oct 15 2008
prev sibling next sibling parent reply John Reimer <terminal.node gmail.com> writes:
Hello Gregor,


 This is what we call a "joke". 

Yet... if it is just a "joke", that implies you are not serious... and yet I do think your parody is meant to make a statement beyond just a "joke". Sorry, I think it's fair to hold you accountable for your "jokes". :) In short, it's not a joke then. Your parody and strong statement of annoyance appear to have been meant to "educate" the community. -JJR
Oct 15 2008
parent reply Gregor Richards <Richards codu.org> writes:
John Reimer wrote:
 Hello Gregor,
 
 
 This is what we call a "joke". 

Yet... if it is just a "joke", that implies you are not serious... and yet I do think your parody is meant to make a statement beyond just a "joke". Sorry, I think it's fair to hold you accountable for your "jokes". :) In short, it's not a joke then. Your parody and strong statement of annoyance appear to have been meant to "educate" the community. -JJR

You think that jokes can't carry messages beyond their humor? That they have to be entirely without serious content? You must live a profoundly humorless life, as the vast, VAST majority of jokes serve as vessels for some sort of message. - Gregor Richards
Oct 16 2008
parent John Reimer <terminal.node gmail.com> writes:
Hello Gregor,

 John Reimer wrote:
 
 Hello Gregor,
 
 This is what we call a "joke".
 

and yet I do think your parody is meant to make a statement beyond just a "joke". Sorry, I think it's fair to hold you accountable for your "jokes". :) In short, it's not a joke then. Your parody and strong statement of annoyance appear to have been meant to "educate" the community. -JJR

they have to be entirely without serious content? You must live a profoundly humorless life, as the vast, VAST majority of jokes serve as vessels for some sort of message. - Gregor Richards

Come now, Gregor, what's with the wild conjectures? Or is this just a hyperbolic joke in which I'm once again missing the message? We're on a roll here! :-) Nope, I just thought that saying it was a "joke" was like equivocating somewhat on your purpose for posting, kind of like an attempt to lighten a situation when you suddently see everyone has got deadly serious. You may "snort" at that suggestion, but you can't avoid perception... well ... you can... but it may come back to bite you. :-) The only real difficulty I have in conversing with you, Gregor, is the mental exercise involved in order to guess whether you are serious or not. If everything is a "joke" or "parody" (with or without a message) for you, which it may not be to others, then communication breaks down. That's all I'm saying. To you this may indicate my level of intelligence by my inability to comprehend; but hey, you got know how to speak to the little guys too (or maybe, you just don't want to). Actually, I feel a little sheepish here. Everytime I get back into this newsgroup, no matter how hard I try, I get pulled into wranglings like this (my fault for asking, I suppose): it's kind of my nature to want mend these sort of issues, and sometimes I mess up big time by getting invovled. I guess I have to learn to leave well enough alone sometimes in a group where everyone has a say. No doubt we all have our peculiarities. I'll stop hounding you on this, Gregor, but I sure wish you would go against your nature sometimes, and cut the scathing sarcasm. You do come across -- perhaps in a parallel vein as superdan minus the foul mouth -- as if you exist at the center of everything. On the other hand, over the last couple of years, I've been able to appreciate other aspects of your character despite the existance of this one. No, not trying to placate you with a final "nice" word... okay... maybe a little. Otherwise, I'm just trying (lamely perhaps) to say that it's "not all bad" and wish you could do better. -JJR
Oct 16 2008
prev sibling parent reply superdan <super dan.org> writes:
Gregor Richards Wrote:

 John Reimer wrote:
 Hello Gregor,
 
 You want to destroy all life on Earth. However, you don't want people
 panicking as this could alter the result, so you want all humans to
 die at the same instant. To do this, you're creating nano-robots. A
 single nano-robot cannot control a persons mind: Seven are required
 (three in each half of the brain and one in the brain stem).
 Nano-robots can harvest material from their host to build new
 nano-robots, but the host will die after approximately twenty
 nano-robots-worth of material has been harvested (they require
 particular rare particles that can only be harvested from the heart
 and lungs). Nano-robots may communicate with one-another via
 broadcast, but the range is limited to 1 mile. Nano-robots do not have
 unique identification globally, but do have unique identification
 within a body (that is, nano-robots in the same body can distinguish
 each other, but broadcast messages from a nano-robot in one human
 cannot implicitly be distinguished from broadcasts from another).
 These broadcasts travel at the speed of light (seeing as that they are
 light). Nano-robots harvest energy from their host, and as such can
 survive indefinitely. A nano-robot in a dead host survives long enough
 that this variable is not relevant for this problem.

 Robots can only be spread by direct physical contact from an infected
 host to an uninfected one, and the process of transferring one
 nano-robot destroys two nano-robots (that is, the infected host loses
 three robots in the process but the new host only gains one).

 Devise an algorithm for these nano-robots that will destroy all human
 life on Earth in a minimum amount of time, but with which all humans
 will be destroyed within five minutes of each other. That is, minimize
 the time from deploying the first nano-robot to the initial human life
 being exterminated, and minimize the time from the initial human life
 being exterminated to all human life being exterminated. You may
 assume a maximum of twelve degrees of separation between average
 industrialized people and that even the most remote tribe is connected
 by at least one human to the industrialized world.

 Bonus: How would you change this algorithm if you wanted to destroy
 all animal life? All life? How would you change it if astronauts were
 considered?

 - Gregor Richards

Ok, Gregor. I'll bite. What's your fascination with this problem? Are you trying to make a point about something? If "yes", you may as well be direct about it. If "no", then why the thread hijacking? Come on... help me out... I'm a little slow sometimes. :) -JJR

Thread hijacking? Seriously? This isn't a forum, there are totally disconnected subthreads within any thread. This is what we call a "joke".

no pal. this is what /you/ call a "joke". wasn't funny the first time. second time looks stupid.
 On the one hand it's a parody of the 
 always-annoying real-life-algorithm thread, on the other hand it's a 
 parody of the needlessly-loaded choice of settings for the 
 oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This 
 problem could be formalized as a simple tree-based message-passing 
 communication problem, but instead we've gone political. Well, so long 
 as war is involved, let's step it up and destroy everything. Yeeee haw.

so ur the sharpest tool in the shed eh. why don't you send in your solution. tree-based message-passing sounds like bullshit you'd say when you have no idea. this is a classic signal propagation problem in circuits, i solved it all the time when i was working on async vlsi. and tree-based message-passing has nothing to do with it. the man made it a story. that /is/ funny. if it annoys u piss off.
Oct 16 2008
parent Gregor Richards <Richards codu.org> writes:
superdan wrote:
 Gregor Richards Wrote:
 
 This is what we call a "joke".

no pal. this is what /you/ call a "joke". wasn't funny the first time. second time looks stupid.

This "we" is what we call the singular "we". So's that one. And with the insults I'm crying on the inside. Actually, I'm laughing, but y'know how sometimes laughing and crying sort of sound similar? Yeah, that's the situation.
 
 On the one hand it's a parody of the 
 always-annoying real-life-algorithm thread, on the other hand it's a 
 parody of the needlessly-loaded choice of settings for the 
 oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This 
 problem could be formalized as a simple tree-based message-passing 
 communication problem, but instead we've gone political. Well, so long 
 as war is involved, let's step it up and destroy everything. Yeeee haw.

so ur the sharpest tool in the shed eh. why don't you send in your solution. tree-based message-passing sounds like bullshit you'd say when you have no idea. this is a classic signal propagation problem in circuits, i solved it all the time when i was working on async vlsi. and tree-based message-passing has nothing to do with it. the man made it a story. that /is/ funny. if it annoys u piss off.

Yes, my joke is my CLAIM OF DOMINANCE. Anyone who uses humor is claiming that they are the greatest of all human beings. HOW DARE YOU SUGGEST OTHERWISE YOU HUMORLESS PIG. It amuses me that my realization of the problem is, to you, a statement that I must be utterly ignorant of everything, but you immediately proceed to make a different realization of the problem. And yet, scanning over the responses, you too haven't posted an actual algorithm. Hey wait, it amuses me, which must mean you were making a joke, which means you're CLAIMING DOMINANCE! Damn! Why is it a tree-based message-passing problem? Because this is software, dingus, not hardware. You have a TREE of actors (or threads, or processes as you prefer. I'll go with actors because they're usually associated with message-passing concurrency). Every actor needs to send MESSAGES to all its subordinates. Why, lo and behold, it's a tree-based message-passing problem! Yeesh. - Gregor Richards
Oct 16 2008
prev sibling next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:gd6ifg$8g3$3 digitalmars.com...
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or she 
 will call them all at once. Cool!

 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.

 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.

Can a subordinate initiate a call to a superior?
Oct 15 2008
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Nick Sabalausky wrote:
 "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
 news:gd6ifg$8g3$3 digitalmars.com...
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or she 
 will call them all at once. Cool!

 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.

 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.

Can a subordinate initiate a call to a superior?

No, but the hierarchy is known in advance. Andrei
Oct 16 2008
prev sibling parent reply Russell Lewis <webmaster villagersonline.com> writes:
The solution here is just like what happens in real life at my company 
when a major reorg is happenning:

* President calls, and all officers call their subordinates immediately, 
until the sergeants hear about it.  Then they wait.
* At a predetermined time (when enough time has elapsed for all 
sergeants to have heard the news), all sergeants call all of their 
platoons at the same moment.
* All of these calls at once overload the VOIP system, which promptly 
crashes.
* Realizing that a VOIP crash generally means that major news is coming, 
all privates log onto the Drudge Report and find out what is going on.

:)

Basic idea is that sergeants can wait arbitrarily long, so you put the 
onus on them to hold the info until the predetermined time.

Andrei Alexandrescu wrote:
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or 
 she will call them all at once. Cool!
 
 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.
 
 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.
 
 
 Good luck!
 
 Andrei

Oct 16 2008
parent reply Don <nospam nospam.com.au> writes:
Russell Lewis wrote:
 The solution here is just like what happens in real life at my company 
 when a major reorg is happenning:
 
 * President calls, and all officers call their subordinates immediately, 
 until the sergeants hear about it.  Then they wait.
 * At a predetermined time (when enough time has elapsed for all 
 sergeants to have heard the news), all sergeants call all of their 
 platoons at the same moment.
 * All of these calls at once overload the VOIP system, which promptly 
 crashes.
 * Realizing that a VOIP crash generally means that major news is coming, 
 all privates log onto the Drudge Report and find out what is going on.
 
 :)
 
 Basic idea is that sergeants can wait arbitrarily long, so you put the 
 onus on them to hold the info until the predetermined time.

Doesn't minimize the number of delays, though. Define the rank of an officer as the maximum number of levels beneath him. Every officer of rank R (who is called at time t=0) should immediately call his subordinate(s) of rank R-1 (ie, at time t=1). Then call others of rank R-K at time K.
 
 Andrei Alexandrescu wrote:
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or 
 she will call them all at once. Cool!

 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.

 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.


 Good luck!

 Andrei


Oct 16 2008
parent Don <nospam nospam.com.au> writes:
Don wrote:
 Russell Lewis wrote:
 The solution here is just like what happens in real life at my company 
 when a major reorg is happenning:

 * President calls, and all officers call their subordinates 
 immediately, until the sergeants hear about it.  Then they wait.
 * At a predetermined time (when enough time has elapsed for all 
 sergeants to have heard the news), all sergeants call all of their 
 platoons at the same moment.
 * All of these calls at once overload the VOIP system, which promptly 
 crashes.
 * Realizing that a VOIP crash generally means that major news is 
 coming, all privates log onto the Drudge Report and find out what is 
 going on.

 :)

 Basic idea is that sergeants can wait arbitrarily long, so you put the 
 onus on them to hold the info until the predetermined time.

Doesn't minimize the number of delays, though. Define the rank of an officer as the maximum number of levels beneath him. Every officer of rank R (who is called at time t=0) should immediately call his subordinate(s) of rank R-1 (ie, at time t=1). Then call others of rank R-K at time K.

Actually, I'm assuming that 'inserting as few delays as possible' means maximizing number of instances where an underling begins receiving his message from his superior as soon as the superior has received it. But that's probably not what Andrei had in mind, since it conflicts with the idea of calling all subordinates at once. Instead: If rank of the root is T: any officer of rank R, should wait for ((rank of highest sibling)-R) time units before passing on the message, except of course if he has rank-and-file soldiers, who should be told seperately after waiting for (rank of highest sibling-1) time units.
 
 Andrei Alexandrescu wrote:
 Let's reconsider the problem of retreating from Iraq, with a twist.
 Grace to new technology, teleconferencing is now possible. All direct
 subordinates of any officer can be called SIMULTANEOUSLY. So there is no
 more need for one officer to call each subordinate in sequence; he or 
 she will call them all at once. Cool!

 However, now the demands also increased. Your task, should you yadda
 yadda, is to devise a schedule for teleconferenced such that EVERY rank
 and file soldier finds the news at EXACTLY the same time. That means you
 must insert some delays in the system. However, you should insert as few
 delays as possible, and also to ensure there is minimal global delay
 from the moment the President picks up the phone to the moment soldiers
 get the news.

 Be warned: this is quite a different problem than the previous one in
 spite of the similarities. You may want to start from scratch instead of
 adapting an algorithm suitable for the previous problem.


 Good luck!

 Andrei



Oct 17 2008