Can anybody please provide the editorial of CUBE CAKES of December Challenge 2013…???
2 Likes
I used prefix sum to solve this Question…maintaining a 3D array a[i][j][k] which store the number of same elements in the cube SA and SB upto the cube formed by the corners (1,1,1) , (1,1,k) ,(1,j,1 ),(1,j,k) ,(i,1,1) ,(i,1,k) , (i,j,1) ,(i,j,k) .This can be done in O(n^3). First Initialise a[i][j][0],a[i][0][j] & a[0][i][j] with zero for all i,j & k(1 to n).now iterate through each cell and each cell a[i][j][k]=a[i-1][j][k]+a[i][j-1][k]+a[i][j][k-1]-a[i][j-1][k-1]-a[i-1][j][k-1]-a[i-1][j-1][k]+a[i-1][j-1][k-1] and if SA[i*N*N + j*N + k]=SB[i*N*N + j*N +k] then increment a[i][j][k] by one.
Now finding the greatest size can be done in O(n^4) for each size S(n to 1) check for all cube’s that can be formed of size S.
check if for any cube of size S (number of same elements)/(sizesizesize)>=P then increment the count.
At the end for any size S ,if count >0 then decrement the size and check all the cube of decremented size otherwize come out of the loop…
after checking the sizes if(size=0) then no cube exits of that percenatge other wise output S and count.
You can view my solution here http://www.codechef.com/viewsolution/3099247
5 Likes
A cube originating at (i, j, k) of size s can be formed from a cube originating at (i, j, k) of size s-1 by just appending 3 planes(i-j, j-k and i-k) to the latter cube. You can maintain prefix sum of each plane in all the three directions to use this method.
You can refer my solution here.
This is a O(n^4) solution. Disadvantage of this method is that memory usage is very high ! Though this is what I did, I think the prefix sum method provided by @hatim009 is much better 
!
but the actual time complexitiy of the problem would be TN4 (=405 =102,400,000) which most likely can give tle. So, is there a better method for this?
Because i also thought of the same procedure and gave up because of the above reason.
What I see is even the best solution uses the same method. I don’t think there is a solution with lower asymptotic time.
U may apply any method to store the common entries(prefix sum) in a 3d array… ( cumilative way ) … and may proceed further .
suppose dp[i][j][k] gives u the number of common elements from (1,1,1) to (i,j,k).
then u may find the number of common elements from (i,j,k) to (xx,yy,zz) as :
**dp[xx][yy][zz]
- dp[i-1][yy][zz] - dp[xx][j-1][zz] - dp[xx][yy][k-1]
- dp[xx][j-1][k-1] + dp[i-1][yy][k-1] + dp[i-1][j-1][zz]
- dp[i-1][j-1][k-1];**
just imagine the blocks in space… you will get it !
1 Like
i should’ve coded and submitted then. I was thinking of better solution and couldn’t think of any.
@hatim009 Sorry for the off-topic, but this is the first time being able to solve 5 questions in codechef long contest apart from the challenge one. I found that nearly three questions were using the similar method (mentioned in the comment), atleast i’ve used it. Is this the same case for almost every contest or it happened only this time?
No this is not the same case for every contest. See the previous months challenges.
ok. i thought that if that is the case i can direct my thinking towards this direction and nothing else. Thanks!
I used the exact same approach but didn’t pass the time limit 
I did the exact same thing as you except for the order of the 4 loops. I put the size loop as the innermost loop and got TLE. Now I changed it as the outermost loop like you and it’s AC! Now I know, too many if condition can cause TLE 
Hi dip_kush04, you can find the editorial here: http://discuss.codechef.com/questions/33778/cube-editorial