Foodletown has a Volunteer Emergency Response Team which assists the police and fire departments. The members are alerted by phone. The police or fire chief will notify the captain of the V.E.R.T., who will notify the members. The captain will call certain members, who may call other members, and so forth. Each caller gives the location and nature of the emergency, and also may give up to 2 pieces of information to direct the phoning process, such as "I have called Smith, but I have not called Jones," or "You call Smith next and I will call Jones next." Assume that each call lasts exactly 1 minute.
How should the calling be organized such that all V.E.R.T. members are notified within the shortest possible time?
You need to address two cases. In the ideal case, every member is reached, and the calling proceeds by a fixed plan.
In the real-world case, there is a 50% chance that any given member is reached. (The captain is always reached.)
In both cases, give the expected number of minutes if the squad has 100 members.
Note: No global database exists of who has been notified so far.
Assuming every member has a complete directory that is (or can be) numbered.
The captain is person 1.
Person 1 calls all powers of 2 in order: 2,4,8,16,32,64
Person 2 calls 1 less than powers of 2: 3,7,15,31,63
Person 3 calls 2 less than powers of 2: 6,14,30,62
Person 4 calls 3 less than powers of 2: 5,13,29,61
Person 5 calls 4 less than powers of 2: 12,28,60
...
Person 29 calls 28 less than powers of 2: 36,100
in this way person 1 is called on minute 0
person 2 is called on minute 1
persons 3&4 are called on minute 2
persons 5,6,7,8 are called on minute 3
...
persons 33 through 64 are called on minute 6
persons 65 through 100 are called on minute 7.
The message can be "As you know, you are person p. Call the people with higher numbers of the form 2^n - p + 1"
This is the ideal case.
In the case 50% of people unreachable, this gets unworkable, though. If 1 can't get 2, do they then call their people and 2's people? This would make the total time double. I think some sort of code to shift the tree branches would work.
|
|
Posted by Jer
on 2023-12-25 12:25:58 |
Ideal case solution?
