Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Bruteforce should do just fine here for n &lt; 100, if properly implemented: solution below has O(n^4) time and O(n^2) memory complexity. 10^8 operations should be well under 1 second on modern PC (especially considering that each operation is very cheap: few additions and subtractions).</p> <p>Some observations</p> <ol> <li>There're O(n^4) sub-rectangles to consider and each of them can be a solution.</li> <li>If we can find number of 1's and 0's in each sub-rectangle in O(1) (constant time), we'll solve problem in O(n^4) time.</li> <li>If we know number of 1's in some sub-rectangle, we can find number of zeroes (through area).</li> </ol> <p>So, the problem is reduced to following: <em>create data structure allowing to find number of 1's in each sub-rectangle in constant time</em>.</p> <p>Now, imagine we have sub-rectangle <code>[i0..i1]x[j0..j1]</code>. I.e., it occupies rows between i0 and i1 and columns between j0 and j1. And let <code>count_ones</code> be the function to count number of 1's in subrectangle.</p> <p>This is the main observation:</p> <pre><code>count_ones([i0..i1]x[j0..j1]) = count_ones([0..i1]x[0..j1]) - count_ones([0..i0 - 1]x[0..j1]) - count_ones([0..i1]x[0..j0 - 1]) + count_ones([0..i0 - 1]x[0..j0 - 1]) </code></pre> <p>Same observation with practical example:</p> <pre><code>AAAABBB AAAABBB CCCCDDD CCCCDDD CCCCDDD CCCCDDD </code></pre> <p>If we need to find number of 1's in D sub-rectangle (3x4), we can do it by taking number of 1's in the whole rectangle (A + B + C + D), subtracting number of 1's in (A + B) rectangle, subtracting number of 1's in (A + C) rectangle, and adding number of 1's in (A) rectangle. <code>(A + B + C + D) - (A + B) - (A + C) + (A) = D</code></p> <p>Thus, we need table <code>sums</code>, for each <code>i</code> and <code>j</code> containing number of 1's in sub-rectangle <code>[0..i][0..j]</code>.<br> You can create this table in O(n^2), but even the direct way to fill it (for each <code>i</code> and <code>j</code> iterate all elements of <code>[0..i][0..j]</code> area) will be O(n^4).</p> <p>Having this table, </p> <pre><code>count_ones([i0..i1]x[j0..j1]) = sums[i1][j1] - sums[i0 - 1][j1] - sums[i1][j0 - 1] + sums[i0 - 1][j0 - 1] </code></pre> <p>Therefore, time complexity O(n^4) reached.</p>
    singulars
    1. This table or related slice is empty.
    1. POFinding the maximum area in given binary data
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNikita Rybak
    1. USNikita Rybak
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI'm afraid that n < 100 is to small data set. Thanks anyway for your investigation.
      singulars
      1. PO
      1. USuser445783
    2. CO@alg0 what complexity do you need, then?
      singulars
      1. PO
      1. USNikita Rybak
    3. COn <= 1000 will be fine.
      singulars
      1. PO
      1. USuser445783
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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