StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This calls for a dynamic programming solution. I'll assume we have a <code>square[r][c]</code> array of booleans which is true if <code>(r, c)</code> has a 1x1 square (I've simplified the solution to work with 1x1, 2x2, 4x4 and 8x8 squares to make it easier to follow, but it's easy to adapt). Pad it with a wall of <code>false</code> <a href="http://www.topcoder.com/tc?module=Static&d1=features&d2=090104" rel="nofollow">sentinel values</a> on the top row and left column.</p> <p>Define a 2d <code>count</code> array, where <code>count[r][c]</code> refers to the number of 1x1 squares in the region above and to the left of <code>(r, c)</code>. We can add them up using a dp algorithm:</p> <pre><code>count[0..n][0..m] = 0 for i in 1..n: for j in 1..m: count[i][j] = count[i-1][j] + count[i][j-1] - count[i-1][j-1] + square[i][j] </code></pre> <p>The above works by adding up two regions we already know the sum of, subtracting the doubly-counted area and adding in the new cell. Using the <code>count</code> array, we can test if a square region is fully covered in 1x1 squares in constant time using a similar method:</p> <pre><code>// p1 is the top-left coordinate, p2 the bottom-right function region_count(p1, p2): return count[p1.r][p1.c] - count[p1.r][p2.c-1] - count[p2.r-1][p1.c] + 2*count[p2.r-1][p2.c-1] </code></pre> <p>We then create a second 2d <code>min_squares</code> array, where <code>min_squares[r][c]</code> refers to the minimum number of squares required to cover the original 1x1 squares. These values can be calculates using another dp:</p> <pre><code>min_squares = count for i in 1..n: for j in 1..m: for size in [2, 4, 8]: if i >= size and j >= size and region_count((i-size, j-size), (i, j)) == size*size: min_squares[i][j] = min(min_squares[i][j], min_squares[i-size-1][j] + min_squares[i][j-size-1] - min_squares[i-size-1][j-size-1] + 1) </code></pre> <p>In order to reconstruct the tiling needed to get the calculated minimum, we use an auxiliary <code>size_used[r][c]</code> array which we use to keep track of the size of square placed at <code>(r, c)</code>. From this we can recursively reconstruct the tiling:</p> <pre><code>function reconstruct(i, j): if i < 0 or j < 0: return place square of size size_used[i][j] at (i-size_used[i][j]+1, j-size_used[i][j]+1) reconstruct(i-size_used[i][j], j) reconstruct(i, j-size_used[i][j]) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload