Gxor | Topcoder Archive

Problem Statement

There is a fixed integer n. All graphs in this problem are undirected unweighted graphs on n vertices. The vertices in each graph are numbered 0 through n-1. Additionally, all graphs are simple, i.e., they do not contain self-loops and multiple edges between the same two vertices.

Given a sequence X of such graphs, the xor of that sequence is again a graph on our n vertices. We will denote this graph XOR(X). For each u and v, vertices u and v are connected by an edge in XOR(X) if and only if the number of graphs in X that contain the edge uv is odd. (In other words, the xor of two graphs is a graph that contains the edge uv if and only if exactly one of those two graphs contains the edge uv. We then extend this definition to a xor of arbitrarily many graphs in exactly the same way that is used to extend the bitwise xor to arbitrarily many integers.)

Given a graph, we can convert it into a string using the following pseudocode:

string(G):
    for u = 0 .. n-1:
        for v = u+1 .. n-1:
            if G contains the edge uv: print 1
            else: print 0

You are given a String[] S that describes a sequence S of n-vertex graphs. Each element of S is the string representation of one of those graphs.

We want to erase some (possibly none, possibly all) graphs from S. Our goal is to produce a sequence T such that XOR(T) is a connected graph. Return the number of ways in which we can do that. (Two ways are considered distinct if the sets of indices of erased graphs differ.)

Note that all n vertices of the graph XOR(T) have to be in the same connected component - there must not be any isolated vertices.

Definition

Class:: Gxor
Method:: countsubs
Parameters:: String[]
Returns:: long
Method signature:: long countsubs(String[] S)
(be sure your method is public)

Constraints

S will contain between 1 and 50 elements, inclusive.
Each element in S will contain exactly n * (n - 1) / 2 characters.
n will be between 2 and 9, inclusive.
Each character in S will be either '0' or '1'.

Examples

```
{"1","1","0"}
```
```
Returns: 4
```
This S contains three 2-vertex graphs. Two of them contain the edge 0-1, one doesn't. In order to have a connected XOR(T) we have to erase exactly one of the first two graphs, and we may or may not erase the last graph.
```
{"011001"}
```
```
Returns: 0
```
```
{"111011"}
```
```
Returns: 1
```
```
{"110","011","101"}
```
```
Returns: 6
```

{"111110","100000","100101","010101"}

Returns: 11

{"110010000000111110101001001001101010",
"101011011000101001111110010000000001",
"010001101100000010010110000001100010",
"101100011110001011101000100010001111",
"111010000010010101010111001000000100",
"101100001101011101101011011001000010",
"111111010000000000110000010101100100"}

Returns: 121

{"000000100000100110001000110001001000","010100001000000000000001001010000000",
"101000100010000100000000010000000010","110001101110110000010000000001000101",
"000001000000010000000110001010100101","100100010001010000000000000010000010",
"111001000000111111001001011001010000","100001100000110001011110000001010001",
"111000000001100100000000000011100000","111010110000011000100000000001101000",
"001000100000001010001001001000011001","110111001101000100000101000100100100",
"100111000010100110001100101101000001","000010100000110111000000000100100000",
"000100001010000000010010000000100100","001100000010010000000100100001100000",
"001000100100000100001000000100010001","011010000110001000000001010011001100",
"000100011111100000000010010010110000","000001010101001010011111100000000110",
"000010000010001010100100010001100000","010001011000000000000100000110000001",
"010000000100100000000000000000011000","100101001000001100000100001000000001",
"100010000000000000000001000000010000","101010000010001001011011000000000100",
"000010000000011010111000010111100100","010001101111000100100101110000100000",
"000110010000000100000000000010000010","111000001000000010010000011100000100",
"000010101100100100010100000000000000","110010001000100100010000000000000000",
"011000100000000100110101101100100001","000100000011001110100000001100111010",
"000110001101100010100000000000010000","000110010010011001010010100110001001",
"110001100000010000000000100100010110","001110011000110000100110000011001000",
"000001000100000110011100000100000101","100001000000010000100000101001101100",
"011010110000011000110011111101011110","010001100010101100000101000000010001",
"011011000101000001101110100011110110","101000001100010010001100011000000010",
"001111000011100001110000010010010001","010000001010010000010000101000110000",
"001101100001000101000100010011001110","001010110110101000010100101101010101",
"000100010111110010010100101000100101","100010000000010101111010010000110001"}

Returns: 1086198432923648

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.