Author: Sergey Nagin Difficulty:Mediumhard PreRequisites:DP(Knapsack) Problem StatementYou are given a fragment of code and binary 3dimensional array $A[0..N1, 0..N1, 0..N1]$, where $N$ can be only power of $2$, $1 <= N <= 32$. Consider all 3dimensional arrays, which can be created with changing no more than $K$ elements of $A$ and apply this code for them. After that, we are interested in finding the minimal and maximal value of resulting function over all such arrays. Below is the fragment of code given in the statement:
ExplanationSubtask 1For this subtask, we can observe that array $A$ has $N^3$ binary cells. Let's compress it in onedimensional array $B$ of size $N^3$. $B_{i*N^2+j*N+k}$ = $A_{i,j,k}$, after that let's iterate over all bitmasks. Assume that $i$th element will be $i$th bit in a mask, then we need to iterate in the range from $0$ to $2^{N^3}1$, check the number of different bits if this number not more than $K$ then launch the code above and relax the minimal and maximal values. Subtasks 25Let's try to understand what is the function $F$ in the statement. Let's make several observations:
What we can do with it? Let's denote couple of functions: In which cases $maxValue[dx..dx+size1,dy..dy+size1,dz..dz+size1][i]$ will be 1? Only in that case if $i = 0$ and all values inside cube are zeroes or ones. Because if $i > 0$, and all the values equal, we can change states exactly $1$ of them, after that value of $F$ will be recalculated using smaller subboxes. In which cases $minValue[dx..dx+size1,dy..dy+size1,dz..dz+size1][i]$ will be 1? Only in those cases when we can receive equal values inside the cube and change not more than $i$ values inside of it. In other words, if $max(zeroes[dx..dx+size1,dy..dy+size1,dz..dz+size1],$ $ones[dx..dx+size1,dy..dy+size1,dz..dz+size1])+i>=size^3$ Otherwise, how to recalculate value of $minValue$ and $maxValue$ using smaller subcubes and values of $minValue$ and $maxValue$ for them. It will be very similar to knapsack problem. $minValue[cube][i]$ can be calculated if we don't change more than $i$ cells inside 8 smaller subcubes. Analogically with $maxValue$. $minValue[cube][i]$ = $min(\sum_{i_{1}+i_{2}+i_{3}+i_{4}+i_{5}+i_{6}+i_{7}+i_{8}=i} minValue[subcube_{1}][i_{1}]+..+minValue[subcube_{8}][i_{8}]$) $maxValue[cube][i]$ = $max(\sum_{i_{1}+i_{2}+i_{3}+i_{4}+i_{5}+i_{6}+i_{7}+i_{8}=i} maxValue[subcube_{1}][i_{1}]+..+maxValue[subcube_{8}][i_{8}]$) It gives us the idea for the next solution:
go(dx, dy, dz, N) //function returns the pair of minValue and maxValue for cube
if N = 1 //If we have only one cell
return {1, 1}, //minValue[0], minValue[1]
{1, 1} //maxValue[0], maxValue[1]
minValue = array of size = N * N * N+1
Total complexity of this algorithm will be $O(N*N*N * log(N) + N*N*N/8 * N*N*N/8 * log(N))$ = $O(N^6*log(N))$, but with very small constant. There are many optimizations for it, the most crucial one is using a onedimensional array instead threedimensional.
Solution:Setter's solution can be found here Please feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 19 Jan '17, 09:30

Another optimization is printing $1,N^3$ if $K=N^3$ which gives you AC from TLE on a subtask. answered 22 Jan '17, 20:33
