Link: contest
Author: viv001@
Tester: gerald@
Denote the two cubes to be A[][][] and B[][][].
For every fixed (x,y), let MaxLineLenXY[x][y][z] be the maximum length of a line with x and y coordinates fixed at (x,y) and ending at z such that the letters on both the lines in the cubes are identical. This can be easily computed as:
MaxLineLenXY[x][y][z]=(A[x][y][z]==B[x][y][z] ? 1+MaxLineLenXY[x][y][z-1] : 0) … (1)
Similarly, let MaxLineLenYZ[x][y][z] and MaxLineLenXZ[x][y][z] be the corresponding lines with fixed (y,z) and (x,z) coordinates.
For every fixed x, let MaxSquareLenX[x][y][z] be the maximum length of a square parallel to the x plane (with x-coordinate=x) ending at (y,z) that is common to both A and B. This can be computed as:
MaxSquareLenX[x][y][z]=(A[x][y][z]==B[x][y][z] ? 1+min(MaxSquareLenX[x][y-1][z-1], MaxLineLenXY[x][y][z-1], MaxLineLenXZ[x][y-1][z]) : 0) … (2)
Similarly, we may compute MaxSquareLenY[x][y][z] and MaxSquareLenZ[x][y][z]
Finally, let MaxCubeLen[x][y][z] be the maximum side of a cube that ends at (x,y,z). This can be computed as:
MaxCubeLen[x][y][z]=(A[x][y][z]==B[x][y][z] ? 1 + min(max_cube_len[x-1][y-1][z-1], MaxSquareLenX[x][y-1][z-1], MaxSquareLenY[x-1][y][z-1], MaxSquareLenZ[x-1][y-1][z], MaxLineLenXY[x][y][z-1], MaxLineLenXZ[x][y-1][z], MaxLineLenYZ[x-1][y][z]) : 0). … (3)
Then you simply compute the maximum value of MaxCubeLen[x][y][z] and count the number of triplets (x,y,z) that attain this maximum.
