CUBE - Editorial

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.

each and every long contest helps us to learn new things,

  1. this problem(cube) is implementation of 3d prefix sum.

  2. rectquer was implementation of 2d prefix sum. :slight_smile:


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 :slight_smile: