StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let <code>B</code> be the list of pairwise sums, with <code>B[0] <= B[1] <= ... <= B[m-1]</code> and let <code>A</code> be the original list of numbers that we're trying to find, with <code>A[0] < A[1] < ... < A[n-1]</code>, where <code>m = n(n-1)/2</code>.</p> <p><strong>Given <code>A[0]</code>, compute <code>A</code> in polynomial time</strong></p> <p>Build <code>A</code> up from smallest element to largest. Suppose that we already know <code>A[0]</code>. Then, since <code>B[0]</code> is the smallest element in <code>B</code>, it can only arise as <code>A[0] + A[1]</code>. Similarly, <code>B[1]</code> must equal <code>A[0] + A[2]</code>. Therefore, if we know <code>A[0]</code>, we can compute <code>A[1]</code> and <code>A[2]</code>.</p> <p>After that, however, this pattern breaks down. <code>B[2]</code> could either be <code>A[0] + A[3]</code> or <code>A[1] + A[2]</code> and without prior knowledge, we cannot know which one it is. However, if we know <code>A[0]</code>, we can compute <code>A[1]</code> and <code>A[2]</code> as described above, and then remove <code>A[1] + A[2]</code> from <code>B</code>. The next smallest element is then guaranteed to be <code>A[0] + A[3]</code>, which allows us to find <code>A[3]</code>. Continuing like this, we can find all of <code>A</code> without ever backtracking. The algorithm looks something like this:</p> <pre><code>for i from 1 to n-1 { // REMOVE SEEN SUMS FROM B for j from 0 to i-2 { remove A[j]+A[i-1] from B } // SOLVE FOR NEXT TERM A[i] = B[0] - A[0] } return A </code></pre> <p>Here's how this works from your example where <code>B = [4,5,7,10,12,13]</code> if we know <code>A[0]=1</code>:</p> <pre><code>start B = [4,5,7,10,12,13] A[0] = 1 i=1: B = [4,5,7,10,12,13] A[1] = 4-1 = 3 i=2: Remove 1+3 from B B = [5,7,10,12,13] A[2] = 5-1 = 4 i=3: Remove 1+4 and 3+4 from B B = [10,12,13] A[3] = 10-1 = 9 end Remove 1+9 and 3+9 and 4+9 from B B = [] A = [1,3,4,9] </code></pre> <p>So it all comes down to knowing <code>A[0]</code>, from which we can compute the rest of <code>A</code>. </p> <p><strong>Compute <code>A[0]</code> in polynomial time</strong></p> <p>We can now simply try every possibility for <code>A[0]</code>. Since we know <code>B[0] = A[0] + A[1]</code>, we know <code>A[0]</code> must be an integer between <code>0</code> and <code>B[0]/2 - 1</code>. We also know that </p> <pre><code>B[0] = A[0] + A[1] B[1] = A[0] + A[2] </code></pre> <p>Moreover, there is some index <code>i</code> with <code>2 <= i <= n-1</code> such that</p> <pre><code>B[i] = A[1] + A[2] </code></pre> <p>Why? Because the only entries potentially smaller than <code>A[1]+A[2]</code> are of the form <code>A[0] + A[j]</code>, and there are at most <code>n-1</code> such expressions. Therefore we also know that</p> <pre><code>A[0] = (B[0]+B[1] - B[i])/2 </code></pre> <p>for some <code>2 <= i <= n-1</code>. This, together with the fact that <code>A[0]</code> lies between <code>0</code> and <code>B[0]/2-1</code> gives only a few possibilities for <code>A[0]</code> to test.</p> <p>For the example, there are two possibilities for <code>A[0]</code>: <code>0</code> or <code>1</code>. If we try the algorithm with <code>A[0]=0</code>, here's what happens:</p> <pre><code>start B = [4,5,7,10,12,13] A[0] = 0 i=1: B = [4,5,7,10,12,13] A[1] = 4-0 = 4 i=2: Remove 0+4 from B B = [5,7,10,12,13] A[2] = 5-0 = 5 i=3: Remove 0+5 and 4+5 from B B = !!! PROBLEM, THERE IS NO 9 IN B! end </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