Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Consider this simpler problem:</p> <blockquote> <p>Given a vector of size N containing only the values 1 and 0, find a subsequence that contains exactly k values of 1 in it.</p> </blockquote> <p>Let <code>A</code> be the given vector and <code>S[i] = A[1] + A[2] + A[3] + ... + A[i]</code>, meaning how many 1s there are in the subsequence <code>A[1..i]</code>.</p> <p>For each <code>i</code>, we are interested in the existence of a <code>j &lt;= i</code> such that <code>S[i] - S[j-1] == k</code>. </p> <p>We can find this in <code>O(n)</code> with a hash table by using the following relation:</p> <p><code>S[i] - S[j-1] == k =&gt; S[j-1] = S[i] - k</code></p> <pre><code>let H = an empty hash table for i = 1 to N do if H.Contains (S[i] - k) then your sequence ends at i else H.Add(S[i]) </code></pre> <p>Now we can use this to solve your given problem in <code>O(N^3)</code>: for each sequence of rows in your given matrix (there are <code>O(N^2)</code> sequences of rows), consider that sequence to represent a vector and apply the previous algorithm on it. The computation of <code>S</code> is a bit more difficult in the matrix case, but it's not that hard to figure out. Let me know if you need more details.</p> <p><strong>Update:</strong> Here's how the algorithm would work on the following matrix, assuming <code>k = 12</code>:</p> <pre><code>0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 </code></pre> <p>Consider the first row alone:</p> <pre><code>0 1 1 1 1 0 </code></pre> <p>Consider it to be the vector <code>0 1 1 1 1 0</code> and apply the algorithm for the simpler problem on it: we find that there's no subsequence adding up to 12, so we move on.</p> <p>Consider the first two rows:</p> <pre><code>0 1 1 1 1 0 0 1 1 1 1 0 </code></pre> <p>Consider them to be the vector <code>0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0</code> and apply the algorithm for the simpler problem on it: again, no subsequence that adds up to 12, so move on.</p> <p>Consider the first three rows:</p> <pre><code>0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 </code></pre> <p>Consider them to be the vector <code>0 3 3 3 3 0</code> and apply the algorithm for the simpler problem on it: we find the sequence starting at position 2 and ending at position 5 to be the solution. From this we can get the entire rectangle with simple bookkeeping.</p>
    singulars
    1. This table or related slice is empty.
    1. PORectangular region in an array
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USIVlad
    1. USIVlad
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PORectangular region in an array
      singulars
      1. PTQuestion
    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. VTAcceptedByOriginator
    1. COWhat do you mean with "sequence of rows in your given matrix"?
      singulars
      1. PO
      1. USyassin
    2. CO@Yassin Ezbakhe - I mean a consecutive sequence of rows. Consider a matrix that has 5 rows numbered 1 to 5. Rows 2, 3 and 4 form a sequence of rows. Treat those rows as a vector (the columns of those rows are elements of the vector) and apply the algorithm for the simpler problem on it. As there are `O(N^2)` such sequences of rows and the algorithm for the simpler problem is `O(N)` and must be applied on all sequences of rows, the total complexity of the solution is cubic.
      singulars
      1. PO
      1. USIVlad
    3. COIf you have the matrix [[0,1,1,1,1,0],[0,1,1,1,1,0],[0,1,1,1,1,0]], how would you extract the 3x4 all ones rectangle?
      singulars
      1. PO
      1. USyassin
 

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