Cube cakes question(dec 2013 challenge)

general
,
1

1.Can anybody explain me this question http://www.codechef.com/problems/CUBE

2.Also suppose

input:
1
3 100
abcdefghijklmnopqrstuvwxyza
abcdefghijklmnopqrstuvwxyzx
o/p:
2 7

How?

2

You can imagine the cube as a 3D array…arr[i][j][k]…Now you fill first array with characters of string-1 in the following fashion:

arr1[0][0][0]=a, arr1[0][0][1]=b, arr1[0][0][2]=c

arr1[0][1][0]=d, arr1[0][1][1]=e, arr1[0][1][2]=f

arr1[0][2][0]=g, arr1[0][2][1]=h, arr1[0][2][2]=i

arr1[1][0][0]=j, arr1[1][0][1]=k, arr1[1][0][2]=l

arr1[1][1][0]=m, arr1[1][1][1]=n, arr1[1][1][2]=o

arr1[1][2][0]=p, arr1[1][2][1]=q, arr1[1][2][2]=r

arr1[2][0][0]=s, arr1[2][0][1]=t, arr1[2][0][2]=u

arr1[2][1][0]=v, arr1[2][1][1]=w, arr1[2][1][2]=x

arr1[2][2][0]=y, arr1[2][2][1]=z, arr1[2][2][2]=a

and the second array as follows:

arr2[0][0][0]=a, arr2[0][0][1]=b, arr2[0][0][2]=c

arr2[0][1][0]=d, arr2[0][1][1]=e, arr2[0][1][2]=f

arr2[0][2][0]=g, arr2[0][2][1]=h, arr2[0][2][2]=i

arr2[1][0][0]=j, arr2[1][0][1]=k, arr2[1][0][2]=l

arr2[1][1][0]=m, arr2[1][1][1]=n, arr2[1][1][2]=o

arr2[1][2][0]=p, arr2[1][2][1]=q, arr2[1][2][2]=r

arr2[2][0][0]=s, arr2[2][0][1]=t, arr2[2][0][2]=u

arr2[2][1][0]=v, arr2[2][1][1]=w, arr2[2][1][2]=x

arr2[2][2][0]=y, arr2[2][2][1]=z, arr2[2][2][2]=x

Now when you’ll imagine this in 3D space…lets say a Rubix cube with each cell having the characters filled as mentioned above…all the cells in two Rubix cubes would match except for the last one…So, the maximum size of a sub cube that matches is 2…You can have 8 distinct sub-cubes of size 2 in a 3x3x3 cube…all of them would match for the given strings except for the last 2x2x2 sub-cube. Hence, there would be 7 sub-cubes of size 2 which match…

2 Likes
3

a cube has 6 faces i.e 54 cells for 3x3x3 cube but we have 27 characters only.So i didn’t get how can we fill characters in cells.
Also, please explain me about
“You can have 8 distinct sub-cubes of size 2 in a 3x3x3 cube”.How?Please help.

4

3x3x3 is 27…each cell is of size 1x1x1…how 6 faces means 54 cells?

5

Regarding 8 distinct sub-cubes of size 2…i can mention the coordinates of body diagonal of the 8 sub-cubes:

  1. [0,0,0] to [1,1,1]

  2. [0,0,1] to [1,1,2]

  3. [0,1,0] to [1,2,1]

  4. [0,1,1] to [1,2,2]

  5. [1,0,0] to [2,1,1]

  6. [1,0,1] to [2,1,2]

  7. [1,1,0] to [2,2,1]

  8. [1,1,1] to [2,2,2],//This one has cell {2,2,2}…So the sub-cube won’t match

Hope this helps you imagine those sub-cubes…

6

no of cells in those 6 faces is 27?then what is the no of cells on each face?

7

Cube being a 3D figure, you can see 9 cells in front-view of each face for a 3x3x3 cube…But the 8 cells touching the boundary contribute to 4 other faces of the cube as well…hence you count each of the boundary cell twice…and the corner cells of each face is counted thrice… as a corner cell of each face contributes to 3 faces of a cube…

You can easily imagine a 3x3x3 cube as a Rubik’s Cube
…This would help you understand how there are only 27 cells…

1 Like
8

yes got it.But don’t know how to proceed further.Does this problem need pure imagination?

9

It needs a lot of imagination…but some optimized algorithm as well…simple brute force won’t work…