You are not logged in. Please login at to post your questions!


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.

asked 31 Dec '13, 23:09

balakrishnan_v's gravatar image

accept rate: 0%

edited 12 Feb '14, 04:10

admin's gravatar image

0★admin ♦♦

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. :)


answered 31 Dec '13, 23:14

squal's gravatar image

accept rate: 14%

edited 01 Jan '14, 19:26

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

This answer is marked "community wiki".

answered 21 Jul '16, 17:14

devuu's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 31 Dec '13, 23:09

question was seen: 3,534 times

last updated: 21 Jul '16, 17:14