×

# CUBE - Editorial

 0 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. asked 31 Dec '13, 23:09 76●5●10●13 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 2 each and every long contest helps us to learn new things, this problem(cube) is implementation of 3d prefix sum. rectquer was implementation of 2d prefix sum. :) answered 31 Dec '13, 23:14 4★squal 1.2k●4●15●33 accept rate: 14%
 0 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 3★devuu 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,764
×16

question asked: 31 Dec '13, 23:09

question was seen: 3,534 times

last updated: 21 Jul '16, 17:14