HalfGraph | Topcoder Archive

Problem Statement

Let G=(V,E) be an undirected graph.

A spanning subgraph of G is a graph that can be created by removing some (possibly empty) subset of edges from G. Note that a spanning subgraph must still contain all vertices of the original graph G.

A spanning subgraph H is called a half of G if the degree of every vertex v in H is exactly half of its degree in G.

You are given String[] a: the adjacency matrix of the graph G. More precisely, a[i][j] is '1' if vertices i and j are connected by an edge, and it is '0' if they are not.

Find and return the adjacency matrix of any graph that is a half of G. If there are multiple answers, you may return any one of them. If there are no answers, output an empty String[] instead.

Definition

Class:: HalfGraph
Method:: compute
Parameters:: String[]
Returns:: String[]
Method signature:: String[] compute(String[] a)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
a has exactly n elements.
Each element of a is a string of length n, consisting of characters '0' and '1' only.
The matrix is symmetric, i.e., for all i,j we have a[i][j] = a[j][i].
The main diagonal contains only characters '0'. In other words, the graph doesn't contain any loops.

Examples

```
{"000",
 "000",
 "000"}
```
```
Returns: {"000", "000", "000" }
```
An empty graph is its own half, because the half of zero is zero.
```
{"01111",
 "10111",
 "11011",
 "11101",
 "11110"}
```
```
Returns: {"00011", "00110", "01001", "11000", "10100" }
```
The input is a complete graph G on five vertices. In the graph G the degree of each vertex is 4. Thus, the output can be any subgraph of G that has 5 vertices and in which the degree of each vertex is 2.
```
{"010",
 "101",
 "010"}
```
```
Returns: { }
```
This graph contains the edges 0-1 and 1-2. It does not have any half, because you cannot have a vertex of degree 1/2.
```
{"01111",
 "10100",
 "11000",
 "10001",
 "10010"}
```
```
Returns: {"00011", "00100", "01000", "10000", "10000" }
```
Remember that the returned graph must be a subgraph of the original one. You are not allowed to add new edges, you may only erase the existing ones.

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.