Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let's say the arrays are <code>A = {A[1] ... A[n]}</code>, and <code>B = {B[1] ... B[n]}</code>, and the pairwise sum array is <code>C = {A[i] + B[j], where 1 &lt;= i &lt;= n, 1 &lt;= j &lt;= n}</code> which has <code>n^2</code> elements and we need to find its median.</p> <p>Median of <code>C</code> must be an element of the array <code>D = {A[1] + B[n], A[2] + B[n - 1], ... A[n] + B[1]}</code>: if you fix <code>A[i]</code>, and consider all the sums <code>A[i] + B[j]</code>, you would see that the <em>only</em> <code>A[i] + B[j = n + 1 - i]</code> (which is one of <code>D</code>) <em>could be</em> the median. That is, it may not be the median, but if it is not, then all other <code>A[i] + B[j]</code> are also not median. </p> <p>This can be proved by considering all <code>B[j]</code> and count the <em>number of values</em> that are <strong>lower</strong> and <em>number of values</em> that are <strong>greater</strong> than <code>A[i] + B[j]</code> (we can do this quite accurately because the two arrays are sorted -- the calculation is a bit messy thought). You'd see that for <code>A[i] + B[n + 1 - j]</code> these two counts are most "balanced".</p> <p>The problem then reduces to finding median of <code>D</code>, which has only <code>n</code> elements. An algorithm such as <a href="http://en.wikipedia.org/wiki/Selection_algorithm" rel="nofollow">Hoare's</a> will work.</p> <p><strong>UPDATE</strong>: this answer is wrong. The real conclusion here is that the <strong>median</strong> is one of <code>D</code>'s element, but then <em><code>D</code>'s median</em> is the not the same as <code>C</code>'s median.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the median of the sum of the arrays
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USKhanh Nguyen
    1. USKhanh Nguyen
    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. VTDownMod
    1. COthis is what aaronman said, isn't it? i thought there was a counter-example?
      singulars
      1. PO
      1. USandrew cooke
    2. COif you can't read deleted posts, consider [0 1 1 1 2] and [0 0 0 1 2]. if i've understood you correctly, your "diagonal" is [2 2 1 1 2] and the median of that is 2. but the correct result is 1.
      singulars
      1. PO
      1. USandrew cooke
    3. COSomone found the solution in the paper, but it would be nice if it could be delivered in code in c++ or java, or at least explained in less mathematical terms than in the paper
      singulars
      1. PO
      1. USaaronman
 

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