Editorial for TLE '16 Contest 4 P3 - Cubes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: d

To solve this problem, it is necessary to choose all possible locations of the 8 corners. This can be done with a permutation.

To check if a position is valid, there should be 12 beams in the proper locations. Any remaining beams do not matter and can be thrown away.

Time complexity: \mathcal{O}(V! * E) where V=8 is the number of corners and E=12 is the number of beams in the cubic frame.

One common mistake is just counting the number of beams that connect to a corner. For 2 tetrahedra, there are 8 corners and 12 beams, and each corner is connected to 3 beams. It is not possible to create a cube from 2 tetrahedra.


There are no comments at the moment.