 # Cube cakes question(dec 2013 challenge)

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?

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=a, arr1=b, arr1=c

arr1=d, arr1=e, arr1=f

arr1=g, arr1=h, arr1=i

arr1=j, arr1=k, arr1=l

arr1=m, arr1=n, arr1=o

arr1=p, arr1=q, arr1=r

arr1=s, arr1=t, arr1=u

arr1=v, arr1=w, arr1=x

arr1=y, arr1=z, arr1=a

and the second array as follows:

arr2=a, arr2=b, arr2=c

arr2=d, arr2=e, arr2=f

arr2=g, arr2=h, arr2=i

arr2=j, arr2=k, arr2=l

arr2=m, arr2=n, arr2=o

arr2=p, arr2=q, arr2=r

arr2=s, arr2=t, arr2=u

arr2=v, arr2=w, arr2=x

arr2=y, arr2=z, arr2=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

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.

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

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…

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

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