Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <blockquote> <p>the main problem is how to count distinct elements of the vector. as you would resolve it?</p> </blockquote> <p>If you allowed to use hashing, you could do the following</p> <pre><code>init Hashtable h distinct_count := 0 for each element v of the vector V if h does not contain v (O(1) time in average) insert v into h (O(1) time in average) distinct_count := distinct_count + 1 return distinct_count </code></pre> <p>This is in average O(n) time.</p> <p>If not here is an O(n log n) solution - this time worst case</p> <pre><code>sort V (O(n log n) comparisons) Then it should be easy to determine the number of different elements in O(n) time ;-) </code></pre> <p><strike>I could also tell you an algorithm to sort V in O(n*b) where b is the bit count of the integers - if this helps you.</strike></p> <p>Here is the algorithm:</p> <pre><code>sort(vector, begin_index, end_index, currentBit) reorder the vector[begin_index to end_index] so that the elements that have a 1 at bit currentBit are after those that have a 0 there (O(end_index-begin_index) time) Let c be the count of elements that have a 0 at bit currentBit (O(end_index-begin_index) time; can be got from the step before) if (currentBit is not 0) call sort(vector, begin_index, begin_index+c) call sort(vector, begin_index+c+1, end_index) </code></pre> <p>Call it with vector = V begin_index = 0 end_index = n-1 currentBit = bit count of the integers (=: b)-1.</p> <p>This even uses dynamic programming as requested.</p> <p>As you can determine very easily this is O(n*b) time with a recursion depth of b.</p>
    singulars
    1. This table or related slice is empty.
    1. POProblem k-subvector using dynamic programming
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNubok
    1. USNubok
    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. This table or related slice is empty.
    1. COyes, but the resolution should I use dynamic programming. then definition of recurrence equation and then algorithm for calculating the optimal solution.
      singulars
      1. PO
      1. USkafka
    2. COThat doesn't really solve the problem. We're supposed to find subsequence, not count the amount of distinct elements in the whole sequence.
      singulars
      1. PO
      1. USNikita Rybak
    3. CO@Nikita Rybak Perhaps you are right - but since Antony told this to be his main problem (does he see a solution that I don't see?) I'm willing to give it. :-)
      singulars
      1. PO
      1. USNubok
 

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