AddElectricalWires

SRM 410 · 2008-07-19 · by SnapDragon

SRM 410 · 2008-07-19 · by SnapDragon · Brute Force, Graph Theory, Recursion

Show categories

Class Name: AddElectricalWires

Return Type: int

Method Name: maxNewWires

Arg Types: (vector<string>, vector<int>)

Problem Statement

You are given an electrical circuit for a home, with a number of nodes possibly connected by wires. Any pair of nodes may be connected by at most one wire, and a node can't be connected to itself. Each node on the circuit is either an electrical outlet for the house or a connection to the main electrical grid. The String[] wires tells you the wires that are already in place; the xth character of the yth element is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. The int[] gridConnections lists the indices of the nodes that are connections to the main electrical grid.

You'd like to make the circuit safer and more redundant by adding as many extra wires to it as possible. The one complication is that no two main grid connections are currently wired together (directly or indirectly), and you must preserve this, or else disaster will result. Determine the maximum number of new wires you can add to the circuit.

Constraints

wires will contain between 1 and 50 elements, inclusive.
Each element of wires will have the same length as wires.
Each element of wires will contain only the characters '0' and '1'.
Character i of element i of wires will be a '0'.
Character i of element j of wires will be the same as character j of element i.
gridConnections will contain between 1 and 50 elements, inclusive.
Each element of gridConnections will be an integer between 0 and length(wires)-1, inclusive.
Each element of gridConnections will be distinct.
Each pair of elements of gridConnections will not index nodes connected by a path of '1's in wires.

Examples

{"000","000","000"}
{0}
Returns: 3

Every valid wire can be added.

{"000","000","000"}
{0,1}
Returns: 1

0 and 1 can't be connected, but 0 and 2 (or 1 and 2) still can be.

{"01","10"}
{0}
Returns: 0

This circuit is already complete.

{"00000","00000","00000","00000","00000"}
{0,1,2,3,4}
Returns: 0

Any connections would be disastrous.

{"01000","10100","01010","00100","00000"}
{2,4}
Returns: 3

{"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}
{49}
Returns: 1225

Largest return value.

{"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}
{4,28,11,15,24,35,17,36,26,48,33,39,19,2,47,49,25,18,32,40,5,21,7,12,14,42,27,6,45,44,30,38,13,37,3,16,29,43,9,22,8,23,20,34,1,10,31,0,46,41}
Returns: 0

Largest gridConnections.

{"01111111111111111111111111111111111111111111111111","10111111111111111111111111111111111111111111111111","11011111111111111111111111111111111111111111111111","11101111111111111111111111111111111111111111111111","11110111111111111111111111111111111111111111111111","11111011111111111111111111111111111111111111111111","11111101111111111111111111111111111111111111111111","11111110111111111111111111111111111111111111111111","11111111011111111111111111111111111111111111111111","11111111101111111111111111111111111111111111111111","11111111110111111111111111111111111111111111111111","11111111111011111111111111111111111111111111111111","11111111111101111111111111111111111111111111111111","11111111111110111111111111111111111111111111111111","11111111111111011111111111111111111111111111111111","11111111111111101111111111111111111111111111111111","11111111111111110111111111111111111111111111111111","11111111111111111011111111111111111111111111111111","11111111111111111101111111111111111111111111111111","11111111111111111110111111111111111111111111111111","11111111111111111111011111111111111111111111111111","11111111111111111111101111111111111111111111111111","11111111111111111111110111111111111111111111111111","11111111111111111111111011111111111111111111111111","11111111111111111111111101111111111111111111111111","11111111111111111111111110111111111111111111111111","11111111111111111111111111011111111111111111111111","11111111111111111111111111101111111111111111111111","11111111111111111111111111110111111111111111111111","11111111111111111111111111111011111111111111111111","11111111111111111111111111111101111111111111111111","11111111111111111111111111111110111111111111111111","11111111111111111111111111111111011111111111111111","11111111111111111111111111111111101111111111111111","11111111111111111111111111111111110111111111111111","11111111111111111111111111111111111011111111111111","11111111111111111111111111111111111101111111111111","11111111111111111111111111111111111110111111111111","11111111111111111111111111111111111111011111111111","11111111111111111111111111111111111111101111111111","11111111111111111111111111111111111111110111111111","11111111111111111111111111111111111111111011111111","11111111111111111111111111111111111111111101111111","11111111111111111111111111111111111111111110111111","11111111111111111111111111111111111111111111011111","11111111111111111111111111111111111111111111101111","11111111111111111111111111111111111111111111110111","11111111111111111111111111111111111111111111111011","11111111111111111111111111111111111111111111111101","11111111111111111111111111111111111111111111111110"}
{28}
Returns: 0

Largest complete circuit.

{"00000000001000000100000000000000000000000000000000","00111000000000000000000000000001001000000000000010","01011000000000000000000000000001001000000000000010","01101000000000000000000000000001001000000000000010","01110000000000000000000000000001001000000000000010","00000000000000000000000000000000000000000000000000","00000000000001010000000000000000000000000000000000","00000000000000000000000000011000010100000000000000","00000000000000000000010101000000100000000000000000","00000000000000000000000000000000000000000101100000","10000000000000000100000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000010000000010000000000000000000000000000000000","00000000000000000010000000000100000000000000000000","00000010000001000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","10000000001000000000000000000000000000000000000000","00000000000000100000000000000100000000000000000000","00000000000000000000000010000010000010000010000000","00000000000000000000000000000000000000000000000000","00000000100000000000000101000000100000000000000000","00000000000000000000000000000000000000000000000000","00000000100000000000010001000000100000000000000000","00000000000000000001000000000010000010000010000000","00000000100000000000010100000000100000000000000000","00000000000000000000000000000000000000000000000000","00000001000000000000000000001000010100000000000000","00000001000000000000000000010000010100000000000000","00000000000000100010000000000000000000000000000000","00000000000000000001000010000000000010000010000000","01111000000000000000000000000000001000000000000010","00000000100000000000010101000000000000000000000000","00000001000000000000000000011000000100000000000000","01111000000000000000000000000001000000000000000010","00000001000000000000000000011000010000000000000000","00000000000000000001000010000010000000000010000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000001000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000010000000000000000000000000000000001100000","00000000000000000001000010000010000010000000000000","00000000010000000000000000000000000000000100100000","00000000010000000000000000000000000000000101000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000100000000000","00000000000000000000000000000000000000000000000000","01111000000000000000000000000001001000000000000000","00000000000000000000000000000000000000000000000000"}
{43,35,25,49,29,38,13,42,10,3}
Returns: 150

Several complete components of random size, connected to the grid. The extra nodes must be joined with the largest one.

{"00001000000000001000000000000011000000000000100000","00000000000000000000000000010000000000000000000000","00000000000100000000000000000000010000010000000000","00000000000000000000000000000000000000000000010000","10000000000000001000000000000010100000000000000000","00000000000000000000100000000100000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000001000000000000001000000000000","00000000000000000000000010000000000000000000000000","00000000000000000000000000010000000000000000000000","00100000000000000000000000000000010000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","10001000000000000000000000000010000000000000000000","00000000000000000000100000000100000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000001000000000000000100000000000","00000100000000000100000000001000000000000000000000","00000000000000000000000000000000010000000000000000","00000000100000000001000000000000000100000100000000","00000000000000000000000000000000000000000000000000","00000000010000000000000000100000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000010000000000000000000000000","01000000001000000000000000000000000000000010000000","00000000000000000000100000000000000000000000000000","00000100000000000100000000000000000000000000000000","10001000000000001000000000000001100000000000000000","10000000000000000000000000000010100000000000100000","00001000000000000000000000000011000000000000000000","00100000000100000000010000000000000000001000000000","00000000000000000000000000000000000000000000000000","00000000000000000000001000000000000000000000000010","00000000000000000000000000000000000000000000000000","00000000100000000000000000000000000000100000000000","00000000000000000001000000000000000001000000000010","00100000000000000000000000000000000000000000000000","00000000000000000000000000000000010000000000000000","00000000000000000000001000000000000000000000000000","00000000000000000000000000010000000000000000000000","00000000000000000000000000000000000000000000000000","10000000000000000000000000000001000000000000000000","00010000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000100100000000000","00000000000000000000000000000000000000000000000000"}
{4,29,49,19,47,46,45,39,26,1}
Returns: 207

Next few cases are the same, except the components aren't complete.

16)

{"00000000000000000000001000000010000000000000000000","00000000000000000000000000000000000000000000011000","00000000000000000000000100000100000000000000000000","00000000000000000000000000000000000000000001000000","00000000000000100000000000000010000000000000000000","00000000000010000000100000000000000000000000000000","00000000000000010000000000000000001000000000000000","00000000001000000000000000000000100000000000000000","00000000000000000100000000000000000000000010000000","00000000000000000000000000010000000000000000000000","00000001000000000000000000000000000000010000000000","00000000000001000000000001000000000000000000000000","00000100000000000000000000000000000010000000000000","00000000000100000000000000000000000000001000000000","00001000000000000010000000000000000000000000000000","00000010000000000000000000010000000000000000000000","00000000000000000000000000000000000000000110000000","00000000100000000000001000000000000000000000000000","00000000000000100000000000000000000000100000000000","00000000000000000000010000000000000000000000000010","00000100000000000000000000000000000000000000000000","00000000000000000001000000000100000000000000000000","10000000000000000100000000000000000000000000000000","00100000000000000000000000000000000000000000010000","00000000000000000000000000001000000000000000000001","00000000000100000000000000100000000000000000000000","00000000000000000000000001000000000000000000100000","00000000010000010000000000000000000000000000000000","00000000000000000000000010000000000000000001000000","00100000000000000000010000000000000000000000000000","10001000000000000000000000000000000000000000000000","00000000000000000000000000000000000001000000100000","00000001000000000000000000000000001000000000000000","00000000000000000000000000000000000100000100000000","00000010000000000000000000000000100000000000000000","00000000000000000000000000000000010000010000000000","00000000000010000000000000000000000001000000000000","00000000000000000000000000000001000010000000000000","00000000000000000010000000000000000000000000000100","00000000001000000000000000000000000100000000000000","00000000000001000000000000000000000000000000000010","00000000000000001000000000000000010000000000000000","00000000100000001000000000000000000000000000000000","00010000000000000000000000001000000000000000000000","00000000000000000000000000100001000000000000000000","01000000000000000000000100000000000000000000000000","01000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000100000000001","00000000000000000001000000000000000000001000000000","00000000000000000000000010000000000000000000000100"}
{43,45}
Returns: 568

Two large linear components.

37)

{"0"}
{0}
Returns: 0

Smallest case.

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

Coding Area

Language: C++17 · define a public class AddElectricalWires with a public method int maxNewWires(vector<string> wires, vector<int> gridConnections) · 157 test cases · 2 s / 256 MB per case