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$ ~8~ corners. This can be done with a permutation.

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

Time complexity: $\mathcal{O}(V! * E)$ ~\mathcal{O}(V! * E)~ where $V=8$ ~V=8~ is the number of corners and $E=12$ ~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$ ~2~ tetrahedra, there are $8$ ~8~ corners and $12$ ~12~ beams, and each corner is connected to $3$ ~3~ beams. It is not possible to create a cube from $2$ ~2~ tetrahedra.

$\text{[math]}$

Comments

There are no comments at the moment.