BridgeBuildingDiv2
SRM 661 · 2015-05-01 · by lg5293
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
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.
{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
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BridgeBuildingDiv2 with a public method int minDiameter(vector<int> a, vector<int> b, int K) · 38 test cases · 2 s / 256 MB per case