You are not logged in. Please login at www.codechef.com to post your questions!

×

SEABOX - Editorial

Practice
Contest

Author: Sergey Nagin
Tester: Istvan Nagy
Editorialist: Misha Chorniy

Difficulty:

Medium-hard

Pre-Requisites:

DP(Knapsack)

Problem Statement

You are given a fragment of code and binary 3-dimensional array $A[0..N-1, 0..N-1, 0..N-1]$, where $N$ can be only power of $2$, $1 <= N <= 32$. Consider all 3-dimensional 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:

int F(box A, int dx = 0, int dy = 0, int dz = 0, int size = N) { vector B = {}; for (int i = dx; i < dx + size; i++) { for (int j = dy; j < dy + size; j++) { for (int k = dz; k < dz + size; k++) { B.push_back(A[i][j][k]); } } } sort(B.begin(), B.end()); if (B[0] == B[size * size * size - 1]) { return 1; } int result = 0; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { result += f(A, dx + i * size / 2, dy + j * size / 2, dz + k * size / 2, size / 2); } } } return result; }

Explanation

Subtask 1

For this subtask, we can observe that array $A$ has $N^3$ binary cells. Let's compress it in one-dimensional 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 2-5

Let's try to understand what is the function $F$ in the statement. Let's make several observations:

  • We always deal with cube(3-dimensional array) $A[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$ in the function $F$
  • If all elements in cube $A[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$ are equal, then result of the function is $1$.
  • Otherwise, we divide our box into 8 equal sub-boxes, and sum the resulting values for them.
  • Variable "size" is a power of 2
  • What we can do with it? Let's denote couple of functions:

  • $minValue[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1][i]$ - the minimal value of function $F$, which we can get, if we'll change not more than $i$ values inside cube $A[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$, $0 <= i <= K$
  • $maxValue[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1][i]$ - the maximal value of function $F$, which we can get, if we'll change not more than $i$ values inside cube $A[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$, $0 <= i <= K$
  • $zeroes[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$ - a number of zeroes inside cube $A[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$
  • $ones[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$ - a number of ones inside cube $A[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1]$
  • In which cases $maxValue[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1][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 sub-boxes.

    In which cases $minValue[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1][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+size-1,dy..dy+size-1,dz..dz+size-1],$

    $ones[dx..dx+size-1,dy..dy+size-1,dz..dz+size-1])+i>=size^3$

    Otherwise, how to recalculate value of $minValue$ and $maxValue$ using smaller sub-cubes 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
    maxValue = array of size = N * N * N+1
    //NNN - is the number of cells which can be changed inside cube was = 0 for i = 0..1 //Iterate over 8 subcubes for j = 0..1 for k = 0..1 was += 1 //number of subcubes which was processed tMinValue, tMaxValue = go(dx + i * (N / 2), dy + j * (N /2), dz + z * (N / 2), N / 2) //Observe that tMinValue and tMaxValue has sizes N * N * N / 8 + 1 nMinValue = array(N * N * N / 8 * was + 1, +1000000) nMaxValue = array(N * N * N / 8 * was + 1, -1000000) //new values of minValue and maxValue, in optimized code, we can get rid of them for v = 0..(N * N * N / 8) * was //combine values like a knapsack problem for u = 0..min(N * N * N / 8, u) //iterate over values for subcube nMinValue[v] = min(nMinValue[v], tMinValue[u] + minValue[v - u]) nMaxValue[v] = max(nMaxValue[v], tMaxValue[u] + maxValue[v - u]) for v = 0..(N * N * N / 8) * was minValue[v] = nMinValue[v] maxValue[v] = nMaxValue[v] //Corner cases, not going into subcubes if max(zeroes[dx..dx+N-1,dy..dy+N-1,dz..dz+N-1],ones[dx..dx+N-1,dy..dy+N-1,dz..dz+N-1]) == N * N * N maxValue[0] = 1 for i = 0..N * N * N if min(zeroes[dx..dx+N-1,dy..dy+N-1,dz..dz+N-1],ones[dx..dx+N-1,dy..dy+N-1,dz..dz+N-1]) + i >= N * N * N minValue[i] = 1 return minValue, maxValue
    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 one-dimensional array instead three-dimensional.

    Solution:

    Setter's solution can be found here
    Tester'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

    mgch's gravatar image

    6★mgch
    3451129
    accept rate: 23%

    edited 22 Jan '17, 17:54

    admin's gravatar image

    0★admin ♦♦
    19.7k350498541


    Another optimization is printing $1,N^3$ if $K=N^3$ which gives you AC from TLE on a subtask.

    link

    answered 22 Jan '17, 20:33

    adkroxx's gravatar image

    6★adkroxx
    306719
    accept rate: 7%

    toggle preview
    Preview

    Follow this question

    By Email:

    Once you sign in you will be able to subscribe for any updates here

    By RSS:

    Answers

    Answers and Comments

    Markdown Basics

    • *italic* or _italic_
    • **bold** or __bold__
    • link:[text](http://url.com/ "title")
    • image?![alt text](/path/img.jpg "title")
    • numbered list: 1. Foo 2. Bar
    • to add a line break simply add two spaces to where you would like the new line to be.
    • basic HTML tags are also supported
    • mathemetical formulas in Latex between $ symbol

    Question tags:

    ×15,498
    ×2,093
    ×1,237
    ×921
    ×125
    ×86
    ×4

    question asked: 19 Jan '17, 09:30

    question was seen: 1,000 times

    last updated: 22 Jan '17, 20:33