BroadcastTree | Topcoder Archive

Problem Statement

N computers can be connected as a rooted tree, in which every computer except the root computer has a unique incoming link from its parent computer.

You need to broadcast a message over the whole tree. At time 0 the root computer starts sending the message to its children computers one by one. Once a computer receives the message from its parent computer, it starts sending the message to its children computers one by one. A computer needs sendTime seconds to send a message and can't send messages to multiple children computers simultaneously. A message needs another passTime seconds to pass through a link and reach its destination computer, once it is sent. Once a message reaches a computer, the computer is considered to have received the message and can immediately start sending it further.

You are to construct a rooted tree of N computers and design a broadcasting procedure such that the time to broadcast a message from the root to all other computers will be minimal. Return that time.

Definition

Class:: BroadcastTree
Method:: minimumBroadcastTime
Parameters:: int, int, int
Returns:: int
Method signature:: int minimumBroadcastTime(int N, int sendTime, int passTime)
(be sure your method is public)

Constraints

N will be between 1 and 1,000, inclusive.
sendTime and passTime will be between 1 and 100, inclusive.

Examples

```
4
```
```
2
```
```
1
```
```
Returns: 6
```
One of the optimal rooted trees is the following. The root computer is #0 and it has two children computers #1 and #2. Computer #1 has one child #3, and computers #2 and #3 have no child. The procedure of broadcasting a message is below. At time 0 computer #0 began to send the message to computer #1. At time 2 computer #0 finished sending to computer #1 and began to send the message to computer #2. At time 3 computer #1 received the message and began to send the message to computer #3. At time 4 computer #0 finished sending to computer #2 and was idle from that time. At time 5 computer #2 received the message. At time 5 computer #1 finished sending to computer #3 and was idle from that time. At time 6 computer #3 received the message and the broadcast was finished.
```
6
```
```
4
```
```
1
```
```
Returns: 14
```
```
4
```
```
5
```
```
1
```
```
Returns: 12
```
```
3
```
```
1
```
```
3
```
```
Returns: 5
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.