StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
4348424
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
3
CommunityOwnedDate
CreationDate
2010-12-03T18:01:21.483
FavoriteCount
0
LastActivityDate
2010-12-03T18:01:21.483
LastEditDate
2017-05-23T11:52:59.493
LastEditorUserId
-1
OwnerUserId
4958
ParentId
4239215
PostTypeId
2
Score
13
ViewCount
0
LastEditorDisplayName
text
Body
The <a href="https://stackoverflow.com/questions/4239215/getting-the-lowest-possible-sum-from-numbers-difference/4239849#4239849">solution by marcog</a> is a correct, non-recursive, polynomial-time solution to the problem — it's a pretty standard DP problem — but, just for completeness, here's a proof that it works, and actual code for the problem. [@marcog: Feel free to copy any part of this answer into your own if you wish; I'll then delete this.] <h3>Proof</h3> Let the list be x1, …, xN. Assume wlog that the list is sorted. We're trying to find K (disjoint) pairs of elements from the list, such that the sum of their differences is minimised. Claim: An optimal solution always consists of the differences of consecutive elements. Proof: Suppose you fix the subset of elements whose differences are taken. Then by the <a href="https://stackoverflow.com/questions/4239215/getting-the-lowest-possible-sum-from-numbers-difference/4239390#4239390">proof given by Jonas Kölker</a>, the optimal solution for just this subset consists of differences of consecutive elements from the list. Now suppose there is a solution corresponding to a subset that does not comprise pairs of consecutive elements, i.e. the solution involves a difference xj-xi where j>i+1. Then, we can replace xj with xi+1 to get a smaller difference, since xi ≤ xi+1 ≤ xj ⇒ xi+1-xi ≤ xj-xi. (Needless to say, if xi+1=xj, then taking xi+1 is indistinguishable from taking xj.) This proves the claim. The rest is just routine dynamic programming stuff: the optimal solution using k pairs from the first n elements either doesn't use the nth element at all (in which case it's just the optimal solution using k pairs from the first n-1), or it uses the nth element in which case it's the difference xn-xn-1 plus the optimal solution using k-1 pairs from the first n-2. The whole program runs in time O(N log N + NK), as marcog says. (Sorting + DP.) <h3>Code</h3> Here's a complete program. I was lazy with initializing arrays and wrote Python code using dicts; this is a small log(N) factor over using actual arrays. <pre><code>''' The minimum possible sum|x_i - x_j| using K pairs (2K numbers) from N numbers ''' import sys def ints(): return [int(s) for s in sys.stdin.readline().split()] N, K = ints() num = sorted(ints()) best = {} #best[(k,n)] = minimum sum using k pairs out of 0 to n def b(k,n): if best.has_key((k,n)): return best[(k,n)] if k==0: return 0 return float('inf') for n in range(1,N): for k in range(1,K+1): best[(k,n)] = min([b(k,n-1), #Not using num[n] b(k-1,n-2) + num[n]-num[n-1]]) #Using num[n] print best[(K,N-1)] </code></pre> Test it: <pre><code>Input 4 2 1515 1520 1500 1535 Output 30 Input 8 3 1731 1572 2041 1561 1682 1572 1609 1731 Output 48 </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POGetting the lowest possible sum from numbers' difference
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USShreevatsaR
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POGetting the lowest possible sum from numbers' difference
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

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.