Connection Status:
Competition Arena > P8XGraphBuilder

P8XGraphBuilder

SRM 527 · 2011-05-25 · by dolphinigle

SRM 527 · 2011-05-25 · by dolphinigle · Dynamic Programming, Graph Theory
Class Name: P8XGraphBuilder
Return Type: int
Method Name: solve
Arg Types: (vector<int>)
Problem Statement

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.


You want to build a graph consisting of N nodes and N-1 edges. The graph must be connected. That is, for each pair of nodes there must be some sequence of edges that connects them. For example, the following picture shows a connected graph with N=5 nodes (dots) and N-1=4 edges (lines connecting pairs of dots):




An edge is adjacent to the two nodes that it connects. The degree of a node in the graph is equal to the number of edges adjacent to the node. For example, the degree of node A in the picture above is 3, while the degree of node B is 1. Note that in your graph the degree of each node will be between 1 and N-1, inclusive.


You are given a int[] scores with N-1 elements. The score of a node with degree d is scores[d-1]. The score of a graph is the sum of the scores of its nodes.


Your method should compute and return the maximum possible score for a graph you can construct.


Notes

  • In your solution, the number of nodes N in your graph can be determined as one plus the length of scores.
  • In your graph, there must be at most one edge connecting any pair of nodes, and an edge cannot connect a node with itself.

Constraints

  • scores will contain between 1 and 50 elements, inclusive.
  • Each element in scores will be between 0 and 10,000, inclusive.
Examples
0)
{1, 3, 0}
Returns: 8

As scores contains 3 elements, we are building a graph with N=4 nodes. Nodes of degree 1 have score 1, nodes of degree 2 have score 3, and nodes of degree 3 have score 0. One possible graph with the highest score looks as follows: In this graph the degrees of the nodes are 1, 2, 2, 1, respectively. The sum of their scores is 1+3+3+1 = 8.

1)
{0, 0, 0, 10}
Returns: 10

One possible solution for this test case is:

2)
{1, 2, 3, 4, 5, 6}
Returns: 12
3)
{5, 0, 0}
Returns: 15
4)
{10000}
Returns: 20000

Submissions are judged against all 278 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class P8XGraphBuilder with a public method int solve(vector<int> scores) · 278 test cases · 2 s / 256 MB per case

Submitting as anonymous