You are not logged in. Please login at www.codechef.com 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

5★balakrishnan_v
7651013
accept rate: 0%

edited 12 Feb '14, 04:10

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 31 Dec '13, 23:14

squal's gravatar image

4★squal
1.2k41533
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 :)

link
This answer is marked "community wiki".

answered 21 Jul '16, 17:14

devuu's gravatar image

3★devuu
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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