Hi, Quintopia,
Maybe you misunderstood my algorithm above.
S_k is a set of ordered pair (i,j)
each time we pop the min(S_k) from S_k, we insert at most 2 element in
it
so its size is in O(k)
I think the following should be more clear:
heap : MIN_HEAP
visited[n][n] = {false} : bool
p : Point(i,j)
output(1,1)
heap.insert(1,1)
for i := 1 to k - 1 do
if heap.empty = true
return
p <- heap.pop
output(p.i, p.j)
if p.i + 1 <= n and visited[p.i + 1][p.j] = false then
heap.insert(p.i + 1, p.j)
visited[p.i + 1][p.j] <- true
if p.j + 1 <= n and visited[p.i][p.j + 1] = false then
heap.insert(p.i, p.j + 1)
visited[p.i][p.j + 1] <- true
each operation of heap takes O(logk) time, so total is O(klogk).
Best regards.
On Dec 1, 3:21 pm, "Quintopia" <[EMAIL PROTECTED]> wrote:
> may be right, but how about this:
>
> On input sorted arrays L and R
> output[0] = L[0]+R[0]
> i=0
> j=0
> p=0
> for n=1 to k-1
> if i+1>size[L]
> if j+1>size[R]
> error "can't get k sums"
> else
> j=j+1
> else if j+1>size[R]
> i=i+1
> else if
> else if L[i+1]+R[j]>R[j+1]+L[i]
> j = j+1
> else
> i=i+1
> output[k] = L[i]+R[j]
>
> I'm fairly certain this is correct, since arrays are sorted and you are
> allowed to output duplicate sums, because this is exactly the merge
> type procedure described by Sri. The only problem is that this is a
> O(k) solution and you said O(k lg k) was optimal. Thus, I am fairly
> certain you misstated some part of the problem.
>
> I think what's missing is that the same element from each array can be
> involved in multiple sums and sums can be of an arbitrary number of
> numbers.
>
> You can add this capability by keeping an array of cumulative sums of
> your minimum sums (i.e. cumsum[n] = cumsum[n-1]+output[n]), and a way
> to mark them when you use them, then comparing the two sums that are
> compared above with each of with:
> -the element of the left array plus the first unmarked elem of the
> cumsum array
> -the element of the right array plus the first unmarked elem of the
> cumsum array
> if either is the next minimum sum, use it.
>
> I recommend using a linked list (of the variety with a pointer from
> head to tail) with a reference moving across it as the means of marking
> (mark by moving reference to right). . .this makes accessing the first
> unmarked element take O(1), and makes adding new cumsums to it O(1).
> If the reference advances to the list head again, refuse to compare
> that value or use it (again). Also, if either of the pointers to L or
> R are incremented, reset this reference to the head of the list.
>
> Now sums using an arbitrary number of numbers and repetitions can be
> used.
>
> And yet the algorithm still seems to take only O(k). Correct me if I'm
> wrong.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
