TriangleFree | Topcoder Archive

Problem Statement

You are given an undirected graph with n vertices numbered 0 through n-1. For each valid i, there is an undirected edge connecting two different vertices x[i] and y[i]. No two edges connect the same pair of vertices.
A triangle is a set of three distinct vertices such that each pair of those vertices is connected by an edge. Formally, three distinct vertices u,v,w are a triangle if the graph contains the edges (u,v), (v,w), and (w,u).
The graph has 2^n subsets of vertices (including the empty set). A subset S of vertices is called triangle-free if and only if no three vertices in S form a triangle.
You are given the description of the graph: the int n and the int[]s x and y. Compute and return the number of triangle-free subsets of vertices of the given graph.

Definition

Class:: TriangleFree
Method:: count
Parameters:: int, int[], int[]
Returns:: long
Method signature:: long count(int n, int[] x, int[] y)
(be sure your method is public)

Constraints

n will be between 1 and 60, inclusive.
x will have between 0 and 60 elements, inclusive.
y will have the same number of elements as x.
Each element of x and y will be between 0 and n-1, inclusive.
For each valid i, x[i] != y[i].
No two edges will connect the same pair of vertices.

Examples

```
4
```
```
{0,1,2,3}
```
```
{1,2,0,2}
```
```
Returns: 14
```
There are 2^4 = 16 subsets in total. Two of them are not triangle-free: {0,1,2} and {0,1,2,3}.
```
5
```
```
{0,0,0,0,1,1,1,2,2,3}
```
```
{1,2,3,4,2,3,4,3,4,4}
```
```
Returns: 16
```
This is a complete graph. Any subset having more than two vertices is not triangle-free.

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

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

Returns: 40

{10,20,30}

{20,30,10}

Returns: 1008806316530991104

{0,0,1,0,0,3,0,0,5,0,0,7,0,0,9,0,0,11,0,0,13,0,0,15,0,0,17,0,0,19,0,0,21,0,0,23,0,0,25,0,0,27,0,0,29,5,2,23,5,20,27,26,22,19,18,13,15,12,7,9}

{1,2,2,3,4,4,5,6,6,7,8,8,9,10,10,11,12,12,13,14,14,15,16,16,17,18,18,19,20,20,21,22,22,23,24,24,25,26,26,27,28,28,29,30,30,1,12,27,22,1,14,5,27,27,15,15,29,7,6,3}

Returns: 578333426763956224

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.