Subcube | Topcoder Archive

Problem Statement

A set of points in 3D is called a sub-cube if it is the subset of vertices of some cube in 3D. The cube may be rotated arbitrarily. Note that any non-empty sub-cube will contain between 1 and 8 points, inclusive.

You are given int[]s X, Y, and Z, each containing N elements. These int[]s describe a set of N distinct points in 3D: for each valid i, there is a point at (X[i], Y[i], Z[i]).

Return the number of non-empty subsets of the N points that are sub-cubes.

Definition

Class:: Subcube
Method:: getCount
Parameters:: int[], int[], int[]
Returns:: long
Method signature:: long getCount(int[] X, int[] Y, int[] Z)
(be sure your method is public)

Constraints

X will contain between 1 and 50 elements, inclusive.
Y, Z will contain the same number of elements as X.
Each element of X, Y, Z will be between -1,000,000 and 1,000,000, inclusive.
All described points will be different.

Examples

```
{0, 0, 0, 0, 1, 1, 1, 1}
```
```
{0, 0, 1, 1, 0, 0, 1, 1}
```
```
{0, 1, 0, 1, 0, 1, 0, 1}
```
```
Returns: 255
```
The eight points in the input form a cube with edge length one. Thus every non-empty subset is a sub-cube. The answer is 2^8-1 = 255.
```
{-2, -1, -0, 1, 2}
```
```
{-2, -1, -0, 1, 2}
```
```
{-2, -1, -0, 1, 2}
```
```
Returns: 15
```
There are five colinear points. Every subset containing at least three elements is not a sub-cube.
```
{3,6,-4,-8,0,0}
```
```
{4,8,3,6,0,0}
```
```
{0,0,0,0,5,10}
```
```
Returns: 23
```
Note that the edges of a cube do not have to be parallel to each axis.

{1, 0, 2, -2, 1, 2, 2, 1, 2, 0, 3, 2, 0}

{2, -3, -1, 2, 3, -3, -1, -2, 2, 1, 0, 2, 0}

{1, -3, 0, 3, 1, 2, 2, 1, -1, -1, 1, 0, -3}

Returns: 97

{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15}

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

{0,1,2,3,4,5,6,7,5,4,3,2,1,0,0,0,0,1,2,3,4,5,6,7,5,4,3,2,1,0}

Returns: 511

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.