BridgeBuilding
SRM 661 · 2015-05-01 · by lg5293
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
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
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.
{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}
43
Returns: 42
{50,10,15,31,20,23,7,48,5,50}
{2,5,1,8,3,2,16,11,9,1}
3
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}
4
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}
5
Returns: 1184
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BridgeBuilding with a public method int minDiameter(vector<int> a, vector<int> b, int K) · 111 test cases · 2 s / 256 MB per case