Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>With most DP problems I try and find a kind of reduce-and-conquer relation. That is, a relation whereby I can cut away from the problem size with each step (like divide and conquer, but usually doesn't divide the problem, it just removes a small part). In this problem (like many others) we can make a very simple observation: Either the first point is in the set of <code>i</code> points, or it isn't.</p> <p>Some notation: Let's say X = {x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>k</sub>}, and denote the reduced set X<sub>n</sub> = {x<sub>n</sub>, x<sub>n+1</sub>, ..., x<sub>k</sub>}.</p> <p>So the observation is that either x<sub>1</sub> is one of the <code>i</code> points, or it isn't. Let's call our <code>i</code>-set finding function MSD(<code>i</code>,X<sub>k</sub>) (minimum sum of distances). We can express that cut-away observation as follows:</p> <p>MSD(<code>i</code>,X<sub>k</sub>) = Either MSD(<code>i-1</code>,X<sub>k-1</sub>) U {x<sub>1</sub>} or MSD(<code>i</code>,X<sub>k-1</sub>)</p> <p>We can formalise the "either or" part by realising a simple way of checking which of those two options it actually is: We run through the set X and calculate the sum of the distances, and check which is actually the smaller. We note at this point, that that check has a running time of <code>ki</code> since we will naively run through each of the <code>k</code> points and grab the minimum distance from points in the set of size <code>i</code>.</p> <p>We make two simple observations regarding base cases:</p> <p>MSD(<code>i</code>,X<sub>i</sub>) = X<sub>i</sub><br> MSD(<code>0</code>,X<sub>n</sub>) = {}</p> <p>The first is that when looking for <code>i</code> points in a set of size <code>i</code> we obviously just take the whole set.<br> The second is that when looking for no points in a set, we return the empty set. This inductively ensures that MSD returns sets of size <code>i</code> (it's true for the case where <code>i=0</code> and by induction is true according to our definition of MSD above).</p> <p>That's it. That will find the appropriate set. Runtime complexity is upper bounded by <code>O(ik * step)</code> where step is our <code>O(ik)</code> check from above. This is because MSD will be run on parameters that range from <code>0-i</code> and X<sub>1</sub> - X<sub>k</sub>, which is a total of <code>ik</code> possible arguments.</p> <p>That leaves us with a runtime of O((ik)<sup>2</sup>).</p> <p>The following part is based on my understanding of the OP's question. I'm not sure if the distance of every point in X from the i-sized subset is the sum of the distances of every point from <em>every other point</em> in the subset, or the sum of the distances of every point in X <em>from the subset itself</em>.<br> I.e. sigma of x in X of (sum of distances of x from every point in the subset) OR sigma of x in X of (distance of x from the subset which is the minimum distance from x to any point in the subset)</p> <p>I assume the latter.</p> <p>We can reduce the runtime by optimising the <code>O(ik)</code> check from above. We notice that the elements are actually sorted (albeit in reverse order in this current notation), since when we add them on we do so always from the right hand side. Assuming they're sorted to begin with, they will be once out of the MSD routine. If they weren't sorted to begin with we can sort them, which will only cost <code>O(klogk)</code> anyway.</p> <p>Once sorted, checking the distance of each point from a point in the set will be <code>k * logi</code> since for each point we do a binary search. This yields a total running time of <code>O(ik * klogi + klogk)</code><br> = O(k<sup>2</sup> * ilogi).</p> <p>Finally, we can express that as O(k<sup>3</sup>logk). Not the fastest solution, but a solution.</p> <p>I'm sure there are even more optimisations, but that's my 2c.</p>
    singulars
    1. This table or related slice is empty.
    1. POdynamic programming algorithm during an interview
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USdavin
    1. USdavin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POdynamic programming algorithm during an interview
      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. VTUndeletion
    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. COHi,Thanks for responding. Can you please explain how you deduced MSD(i,Xk) = Either MSD(i-1,Xk-1) U {x1} or MSD(i,Xk-1)? Regards,
      singulars
      1. PO
      1. USuser976078
    2. CO@user976078, that is indeed the key observation. Well, the set you are looking for is well-defined. It might not be unique although at least one such set definitely exists (proof: there are a finite amount of subsets of X of size i, therefore a well-defined property guarantees at least one minimum). If so, I can ask myself a question: is `x1` (the first element in X) in one of these minimum sets? At the outset I have no way of knowing. But I know that it either is, or it isn't. Right?
      singulars
      1. PO
      1. USdavin
    3. COSo now, I don't have to solve the larger problem of finding a minimum i sized subset of X, but rather it's enough to solve a slightly smaller problem: I want to be able to find MSD(i-1,Xk-1) which is an i-1 sized subset of Xk-1 which is a smaller set than X. That's useful if I assume that x1 **is** in one of these minimum sets. Although like we said, maybe it isn't. So I also want to be able to solve MSD(i,Xk-1), which is an i sized subset of Xk-1, again a slightly smaller problem. This solution would be useful is x1 **isn't** in one of these minimum sets.
      singulars
      1. PO
      1. USdavin
 

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