Subcube
SRM 606 · 2013-12-22 · by ir5
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
Return the number of non-empty subsets of the N points that are sub-cubes.
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.
{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
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Subcube with a public method long long getCount(vector<int> X, vector<int> Y, vector<int> Z) · 96 test cases · 2 s / 256 MB per case