GeodesicClosure | Topcoder Archive

Problem Statement

Given a directed graph g, and a set s of nodes in that graph, determine the minimum sized subgraph such that for all pairs of nodes (a,b) in s, if there was a shortest path of length k from a to b in the original graph, there is still a shortest path of length k from a to b in the subgraph.

g will be a square String[] (same number of characters per element as elements), where character i of element j is '1' if there is a directed edge from j to i, and '0' otherwise.

Definition

Class:: GeodesicClosure
Method:: size
Parameters:: String[], int[]
Returns:: int
Method signature:: int size(String[] g, int[] s)
(be sure your method is public)

Notes

There is always a path of length 0 from a node to itself.
G' is a subgraph of G if the nodes in G' are a subset of the nodes in G, and the edges in G' are a subset of the edges in G. The size of any graph is simply the number of nodes.

Constraints

g will have between 1 and 20 elements, inclusive.
g will be square, and each character will be '0' or '1'.
s will have between 1 and the number of elements in g, inclusive.
Each element of s will be between 0 and the number of elements in g - 1, and s will contain no duplicates.
There are no edges of the form (i,i).

Examples

{"0110",
 "0001",
 "0001",
 "0000"}

{0,3}

Returns: 3

{"01100000000000000000",
 "10011000000000000000",
 "10011000000000000000",
 "01100110000000000000",
 "01100110000000000000",
 "00011001100000000000",
 "00011001100000000000",
 "00000110011000000000",
 "00000110011000000000",
 "00000001100110000000",
 "00000001100110000000",
 "00000000011001100000",
 "00000000011001100000",
 "00000000000110011000",
 "00000000000110011000",
 "00000000000001100110",
 "00000000000001100110",
 "00000000000000011001",
 "00000000000000011001",
 "00000000000000000110"}

{0,19}

Returns: 11

```
{"00","00"}
```
```
{0,1}
```
```
Returns: 2
```
```
{"010",
 "001",
 "100"}
```
```
{0,2}
```
```
Returns: 3
```

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.