DnsServersArrangement | Topcoder Archive

Problem Statement

You are given a computer network of N computers enumerated from 0 to N-1. Computer 0 is the one gateway to the global network. Each of the other computers has exactly one parent computer through which all its outgoing packets are sent. This guarantees that the network forms a tree. Each parent computer has a smaller number than all of its children.

Some of the computers in the network are DNS servers. If a computer is a DNS server, it can resolve host names by itself. Otherwise, when it wants to resolve a host name, it will send a DNS request to its parent. If its parent is a DNS server, it will resolve the host, and otherwise, it will send a request to its parent, and so on until a DNS server is found.

You are given a int[] parent, the i-th element of which is the parent of computer i+1. You are also given a int[] d, the i-th element of which is the distance between computer i+1 and its parent. Finally, you are given a int[] significance, the i-th element of which is the significance of computer i+1. Each of these int[]s contains exactly N-1 elements.

You must select exactly K computers in the network to be DNS servers. Every computer must be able to resolve hosts, so the gateway (computer 0) will always be one of those K computers. The penalty of the network is the sum of significance*resolveDistance for each computer, where resolveDistance is the distance to the nearest DNS server. The gateway will always have a resolveDistance of 0, so its significance does not need to be know to calculate the penalty. Return the minimum penalty that can be achieved for this network.

Definition

Class:: DnsServersArrangement
Method:: minPenalty
Parameters:: int[], int[], int[], int
Returns:: int
Method signature:: int minPenalty(int[] parent, int[] d, int[] significance, int K)
(be sure your method is public)

Constraints

parent, d and significance will each contain between 1 and 50 elements, inclusive.
parent, d and significance will each contain the same number of elements.
The i-th element of parent will be between 0 and i, inclusive.
Each element of d will be between 1 and 1000, inclusive.
Each element of significance will be between 1 and 1000, inclusive.
K will be between 1 and N, inclusive, where N-1 is the number of elements in d.

Examples

{0, 1, 2, 3}

{1, 1, 1, 1}

{1, 1, 1, 1}

Returns: 10

The only DNS server is the gateway.

```
{0, 1, 2}
```
```
{1, 1, 1}
```
```
{1, 1, 1}
```
```
2
```
```
Returns: 2
```
```
{0, 1, 2}
```
```
{2, 3, 4}
```
```
{2, 4, 16}
```
```
2
```
```
Returns: 24
```
The gateway and the computer farthest from the gateway are DNS servers.
```
{0, 0, 1, 1}
```
```
{1, 2, 1, 2}
```
```
{2, 1, 2, 1}
```
```
5
```
```
Returns: 0
```
Since each computer is a DNS server, the penalty is 0.

{0, 1, 0, 3, 3, 3}

{3, 2, 4, 2, 4, 5}

{5, 3, 5, 6, 7, 6}

Returns: 100

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.