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][z1] : 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 xcoordinate=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][y1][z1], MaxLineLenXY[x][y][z1], MaxLineLenXZ[x][y1][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[x1][y1][z1], MaxSquareLenX[x][y1][z1], MaxSquareLenY[x1][y][z1], MaxSquareLenZ[x1][y1][z], MaxLineLenXY[x][y][z1], MaxLineLenXZ[x][y1][z], MaxLineLenYZ[x1][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. asked 31 Dec '13, 23:09

each and every long contest helps us to learn new things,
answered 31 Dec '13, 23:14

The editorial given is quite good a method for finding the answer when p is fixed at 100, or in other words, when we are asked to find the largest cube which is exactly similar, and also the no. of such largest dimension cubes..However, the above method doesn't seem to work for p<100. If there's any method, one is encouraged to comment it here in the comment section. Thanks :)
link
This answer is marked "community wiki".
answered 21 Jul '16, 17:14
