BridgeBuilding | Topcoder Archive

Problem Statement

This problem has a non-standard time limit: 3 seconds.

You have two rows of nodes. Each row contains N nodes, numbered 0 through N-1 from the left to the right.

Within each row, adjacent nodes are already connected by edges. You are given the lengths of these edges as int[]s a and b, each containing N-1 elements. For each valid i, a[i] is the length of the edge between nodes i and (i+1) in the top row, and b[i] is the length of the edge between nodes i and (i+1) in the bottom row.

You want to add exactly K new edges to this graph. Each of the new edges must be vertical -- i.e., it must connect some vertex i in the top row to the vertex i in the bottom row. All new edges will have length 0.

By adding the K new edges we will produce a connected graph. The diameter of this graph is the maximum of all shortest distances among pairs of its nodes. In other words, the diameter is the smallest number D such that it is possible to travel from any node to any other node using a path of length D or less.

Given a, b, and the int K, compute and return the smallest possible diameter of the resulting graph.

Definition

Class:: BridgeBuilding
Method:: minDiameter
Parameters:: int[], int[], int
Returns:: int
Method signature:: int minDiameter(int[] a, int[] b, int K)
(be sure your method is public)

Constraints

N will be between 2 and 200, inclusive.
a,b will contain exactly N-1 elements each.
K will be between 1 and N, inclusive.
Each element of a,b will be between 1 and 50, inclusive.

Examples

```
{2,1,1,1,2}
```
```
{1,9,1,9,1}
```
```
4
```
```
Returns: 6
```
One example of an optimal solution is to draw the bridges as follows:

{1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50}

{50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1,50,1}

Returns: 42

{50,10,15,31,20,23,7,48,5,50}

{2,5,1,8,3,2,16,11,9,1}

Returns: 124

{50,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,50}

Returns: 17

{2,4,10,2,2,22,30,7,28,14,17,6,32,41,1,3,16,20,40,39,6,4,18,3,3,7,
 3,2,2,14,10,6,38,6,13,3,6,1,23,26,9,17,1,38,1,21,2,12,3,13,28,6,4,
10,3,1,1,43,15,11,18,6,41,1,2,5,6,26,43,9,5,13,1,27,1,33,12,16,1,12,
1,37,34,6,20,3,21,3,1,17,3,10,2,1,8,25,2,6,7,1,7,22,11,8,49,9,1,7,1,
13,17,20,27,31,43,1}

{5,26,1,2,6,2,16,3,15,1,1,38,2,4,6,1,2,3,11,2,2,2,25,16,2,15,45,3,10,
4,17,5,6,1,16,13,29,3,1,2,4,47,4,10,1,2,23,3,29,20,4,21,1,28,7,25,6,6,
10,1,2,1,17,6,1,28,2,2,12,2,3,42,39,11,18,3,15,4,1,15,3,9,4,26,4,13,41,
1,27,1,14,1,2,14,5,33,1,34,5,17,23,3,33,14,23,2,29,18,3,41,1,45,5,4,6,2}

Returns: 1184

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.