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?
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[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…
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.
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:
[0,0,0] to [1,1,1]
[0,0,1] to [1,1,2]
[0,1,0] to [1,2,1]
[0,1,1] to [1,2,2]
[1,0,0] to [2,1,1]
[1,0,1] to [2,1,2]
[1,1,0] to [2,2,1]
[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
…This would help you understand how there are only 27 cells…
yes got it.But don’t know how to proceed further.Does this problem need pure imagination?
It needs a lot of imagination…but some optimized algorithm as well…simple brute force won’t work…