Problem Statement
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
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
Definition
- Class:
- BridgeBuildingDiv2
- 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 11, 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}
{50,1,50,1,50,1,50,1}
9
Returns: 8
{50,10,15,31,20,23,7,48,5,50}
{2,5,1,8,3,2,16,11,9,1}
3
Returns: 124
{2,4,10,2,2,22,30,7,28}
{5,26,1,2,6,2,16,3,15}
5
Returns: 54
{1,4,7,3,24,39}
{5,11,37,11,1,26}
3
Returns: 52
{34,14,9,2,6}
{25,30,2,22,23}
5
Returns: 56
{3,40,33,3,7,1,10,35,1}
{1,15,6,1,2,19,11,1,27}
4
Returns: 63
{1,24,2,36,16}
{10,23,7,29,4}
4
Returns: 63
{2,1,16,35,1,9,1,5}
{30,2,1,21,8,13,3,1}
3
Returns: 53
{4,1,6,1,1,4,36,5,2}
{46,11,8,8,13,1,8,1,2}
2
Returns: 74
{2,2,38,37,8,1,42,4}
{1,12,1,4,8,16,41,39}
2
Returns: 126
{13,28,19,2,19,6,13}
{5,1,2,2,1,11,28}
2
Returns: 73
{7,1,1,36}
{20,20,7,19}
2
Returns: 55
{3,4,8,1,4,1,23,4}
{8,18,2,27,2,6,1,11}
2
Returns: 59
{2,31,10,9,2,3,47,16,12}
{1,27,23,17,3,8,14,4,46}
6
Returns: 83
{4,4,2,2,45,4,45,1}
{4,23,2,11,17,1,1,25}
3
Returns: 68
{2,3,31,24,1}
{23,14,1,4,30}
5
Returns: 20
{20,2,3,1}
{7,39,1,5}
2
Returns: 28
{2,4,6,8,10,12,14,16,18,20}
{20,18,16,14,12,10,8,6,4,2}
11
Returns: 60
{4,25,22,45,2}
{19,45,12,12,4}
4
Returns: 57
{36,36,22,12,14,14,6}
{43,10,41,20,21,1,5}
5
Returns: 107
{34,22,34,4,6,46,45}
{30,2,43,49,31,6,21}
2
Returns: 184
{11,21,7,5,14}
{10,2,36,24,26}
5
Returns: 39
{9,37,1,22}
{28,32,1,23}
2
Returns: 70
{22,26,16,4}
{5,38,26,13}
2
Returns: 73
{6,37,35,41,19,32,13,41,6}
{26,50,3,19,19,22,39,40,23}
2
Returns: 231
{45,35,36,33}
{4,27,12,13}
2
Returns: 101
{12,26,2,9,12,4,5,3}
{33,7,19,47,5,13,41,4}
3
Returns: 78
{33,13,31,23,22}
{36,29,17,22,34}
2
Returns: 125
{23,16,4,29,35}
{45,25,29,25,2}
2
Returns: 114
{11,46,16,16,14}
{30,33,36,23,22}
4
Returns: 98
{6,8,15,48}
{33,36,4,34}
2
Returns: 87
{21,27,38,43,4,19,19}
{4,9,15,23,9,3,38}
3
Returns: 105
{18,9,15,33,43,43,19,12,29}
{15,34,24,17,17,36,7,13,18}
4
Returns: 150
{11,40,23,1,9,36}
{3,20,6,8,12,25}
2
Returns: 90
{7,22,13,45,13,37,17}
{28,37,50,19,20,11,48}
5
Returns: 117
{50, 10, 15, 31, 20, 23, 7, 48, 5, 50 }
{2, 5, 1, 8, 3, 2, 16, 11, 9, 1 }
3
Returns: 124
{2, 3, 4, 5, 6, 7, 8, 9, 1, 2 }
{3, 4, 2, 1, 3, 4, 5, 2, 1, 1 }
7
Returns: 24