RGBGraph | Topcoder Archive

Problem Statement

Roy and Biv have an undirected graph. Each edge of the graph has a weight and a color. Weights are positive integers. There are exactly three colors of edges: red, green, and blue. These are represented by the characters 'R', 'G', or 'B', respectively.

The graph has n nodes, numbered 0 through n-1. The graph has m edges. For each valid i, there is an edge that connects nodes a[i] and b[i], and this edge has weight w[i] and color c[i]. There may be multiple edges between the same two vertices, and there may even be self-loops in the graph.

For a fixed positive integer k, consider the following task: Roy and Biv want to choose exactly k edges of their graph and erase all other edges. They want to do this in such a way that when they look at the graph with just the k edges they have chosen, they will both see that the entire graph is connected. However, there is a catch: Roy cannot see the color red and Biv cannot see the color blue. Therefore, they have to choose the edges in such a way that the blue and green edges are enough to connect all nodes, and also the red and green edges are enough to connect all nodes. If this is not possible, let answer(k) = -1. Otherwise, let answer(k) be the smallest possible total weight of a set of k edges with the above property.

Return a int[] with m elements: { answer(1), answer(2), ..., answer(m) }.

Definition

Class:: RGBGraph
Method:: findCosts
Parameters:: int, int[], int[], int[], String
Returns:: int[]
Method signature:: int[] findCosts(int n, int[] a, int[] b, int[] w, String c)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
m will be between 1 and 50, inclusive.
a, b, w will have exactly m elements.
Each element of a, b will be between 0 and n-1, inclusive.
Each element of w will be between 1 and 1,000, inclusive.
c will have exactly m characters.
Each character of c will be either 'R', 'G', or 'B'.

Examples

```
4
```
```
{0,1,0,2,2,2}
```
```
{1,2,3,3,3,3}
```
```
{100,4,3,100,1,2}
```
```
"GBRGBR"
```
```
Returns: {-1, -1, -1, 207, 110, 210 }
```
There are no valid sets with 1, 2, or 3 edges. For 4 edges, we can take the edges 0, 1, 2, 3. For 5 edges, we can take the edges 0, 1, 2, 4, 5. For 6 edges, we can take the edges 0, 1, 2, 3, 4, 5.

{0,1,2,1}

{1,2,0,1}

{1,1,1,1}

"RBBR"

Returns: {-1, -1, -1, -1 }

There are no valid sets of any size.

{3,0,4,3,0,0,0,1,4,1}

{4,1,3,2,4,1,2,0,3,0}

{3,2,1,5,1,5,3,4,5,2}

"GBBGRRGRRR"

Returns: {-1, -1, -1, -1, 15, 14, 17, 21, 26, 31 }

{1,3,5,4,1,2,1,5,6,3,3,6,6,3,4,5,4,1,0,6}

{4,4,2,5,6,3,4,0,3,0,1,5,5,5,6,2,0,5,2,5}

{10,6,10,4,1,1,10,1,8,1,8,3,9,1,1,3,4,1,7,8}

"GRBBBBBBBGBGGRRGGGBR"

Returns: {-1, -1, -1, -1, -1, 22, 14, 13, 14, 17, 21, 27, 34, 42, 50, 58, 67, 77, 87, 97 }

{5, 4, 11, 12, 10, 14, 3, 11, 9, 3, 10, 6, 13, 1, 5, 2,
1, 14, 2, 10, 1, 13, 1, 10, 8, 0, 10, 6, 1, 9, 5, 0, 4,
8, 8, 14, 5, 11, 10, 12, 8, 10, 13, 7, 14, 7, 2, 12, 12, 11}

{7, 4, 8, 8, 11, 12, 8, 1, 13, 2, 4, 14, 4, 7, 13, 7, 7,
14, 4, 10, 10, 3, 6, 7, 3, 5, 12, 10, 5, 8, 2, 7, 11, 13,
2, 12, 2, 3, 5, 5, 4, 5, 14, 13, 7, 0, 4, 6, 1, 6}

{10, 5, 2, 6, 3, 3, 1, 4, 6, 6, 8, 2, 7, 3, 3, 2, 8, 8, 1,
10, 10, 10, 3, 1, 6, 8, 3, 2, 6, 10, 8, 1, 1, 8, 6, 3, 6,
9, 6, 1, 6, 10, 3, 6, 3, 4, 5, 4, 3, 10}

"GBGBRBRBBRRGBGRBBRBRGGRBGGRGRRGGBRGGGBRRRGBBGGRBBB"

Returns: {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 74, 69, 65, 63, 64, 65, 68, 71, 74, 77, 81, 85, 89, 94, 100, 106, 112, 118, 124, 130, 136, 143, 151, 159, 167, 175, 183, 191, 200, 210, 220, 230, 240, 250, 260 }

{0,0,0,0,0,0,0,0}

{0,0,0,0,0,0,0,0}

{1,2,3,4,5,6,7,8}

"BBBBBBRG"

Returns: {1, 3, 6, 10, 15, 21, 28, 36 }

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.