Editorial for Upside-Down

Let us assume the given vertices of the tetrahedron are A(Ax,Ay,Az)A( Ax, Ay, Az), B(Bx,By,Bz)B( Bx, By, Bz), C(Cx,Cy,Cz)C(Cx,Cy, Cz), and D(Dx,Dy,Dz)D(Dx, Dy, Dz). According to the given constraints, Az=Bz=CzAz = Bz = Cz. Let us assume Az=Bz=Cz=dAz = Bz = Cz= d. Since the origin is the center of mass, therefore Az+Bz+Cz+Dz=0Az+Bz+Cz+Dz = 0. It is trivial to show from this that Dz=3dDz = -3d.

Now, for a given value of kk, the following transformations will take place:

  • Mirroring the tetrahedron with respect to the XYXY plane: AA becomes A(Ax,Ay,d)A’(Ax, Ay, -d), B(Bx,By,d)B( Bx, By, -d), C(Cx,Cy,d)C(Cx,Cy, -d), D(Dx,Dy,3d)D(Dx,Dy,3d).

  • After mirroring, multiply each coordinate with a factor. The vertices become: A(kAx,kAy,kd)A’(kAx, kAy, -kd), B(kBx,kBy,kd)B’( kBx, kBy, -kd), C(kCx,kCy,kd)C’(kCx,kCy, -kd) and D(kDx,kDy,3kd)D’(kDx,kDy,3kd).

  • After the translation operation, DD’ needs to have a ZZ co-ordinate of dd. Therefore, the translation along positive z-axis direction applied to each point would be d3kdd-3kd. After applying this translation to all the points, the coordinate of vertices becomes: A(kAx,kAy,d2kd)A’(kAx, kAy, d-2kd), B(kBx,kBy,d2kd)B’( kBx, kBy, d-2kd), C(kCx,kCy,d2kd)C’(kCx,kCy, d-2kd) and D(kDx,kDy,d)D’(kDx,kDy,d).

Now, we need to check if tetrahedron ABCDA’B’C’D’ fits inside tetrahedron ABCDABCD or not. The tetrahedron ABCDA’B’C’D’ fits inside ABCDABCD if and only if points AA’, BB’, CC’ and DD’ all are situated on the inside of tetrahedron ABCDABCD.

Now, how can we test if a point P is inside a tetrahedron ABCDABCD? An O(1)O(1) approach would be to notice that if point PP is inside tetrahedron ABCDABCD, then the following equation holds.

Volume( tetrahedron ABCDABCD) = Volume( tetrahedron PBCDPBCD)+Volume( tetrahedron APCDAPCD) +Volume( tetrahedron ABPDABPD) +Volume( tetrahedron ABCPABCP).

The following equation can be used for calculating the volume:

Volume(ABCD)=AxAyAz1BxByBz1CxCyCz1DxDyDz1Volume(ABCD) = \begin{vmatrix}A_x & A_y & A_z & 1\\B_x & B_y & B_z & 1\\C_x & C_y & C_z & 1\\D_x & D_y & D_z & 1\end{vmatrix}

Now we have a technique to verify if for a specific value of k, the transformed tetrahedron (TT’) fits inside the original tetrahedron (TT) or not. To find the maximum value of kk for which TT’ fits perfectly inside TT, notice that by making kk bigger or smaller, we can define how big or how small TT’ is. Also notice that if a transformed tetrahedron fits inside TT, then scaled-down versions of that tetrahedron will also fit inside TT. Therefore, we could run a binary search on kk from the values 00 to 11 and find the biggest value of kk for which TT’ fits inside TT.

Testing if TT’ fits inside TT for a specific value of kk is O(1)O(1). The binary search can either be terminated when the high and low values are sufficiently close.

Statistics


67% Solution Ratio

aropanEarliest, 4M ago

aropanFastest, 0.5s

aropanLightest, 1.0 MB

BigBagShortest, 2886B

Toph uses cookies. By continuing you agree to our Cookie Policy.