Author |
Topic: Find n-th sum of constant number of sorted arrays (Read 3103 times) |
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
 |
Find n-th sum of constant number of sorted arrays
« on: May 5th, 2009, 11:05pm » |
 Quote  Modify
|
Generalisation of find n-th sum of two sorted arrays of n integers: [edit]from here or here[/edit]
A1[1,...,n],A2[1,...,n],...,Ak[1,...,n] are sorted arrays.
Find value of n-th sum among A1i1+A2i2+...+Akik
Interesting cases are k=3,k=4.
|
| « Last Edit: Jun 13th, 2009, 3:41pm by Hippo » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #1 on: May 6th, 2009, 1:42am » |
Quote Modify
|
We can reduce two array to one in O(n log n) time, I think (it's akin to getting the first n elements from merging n arrays of size n). So O(n k log n) should be possible, at least.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #2 on: May 6th, 2009, 2:54am » |
Quote Modify
|
on May 6th, 2009, 1:42am, towr wrote:| We can reduce two array to one in O(n log n) time, I think (it's akin to getting the first n elements from merging n arrays of size n). So O(n k log n) should be possible, at least. |
|
hint: For k=3 there exists o(n) solution. (Let k>3 be discussed later  )
BTW: I distinguish o(n) from O(n).
hint2: The hyperboloid volume increases very slowly with dimension increase.
|
| « Last Edit: May 6th, 2009, 12:12pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #3 on: May 7th, 2009, 3:37pm » |
Quote Modify
|
Hmmm. Noone interested. May be the running time I can achieve O(k\sqrtn logkn). Actually looking from m-th sum for rather small m O(k\sqrtm logkn). With this hint the solution is rather straightforward...
And for m\in \Omega(n2/log n) O(n log m*logk-2n) modification works
|
| « Last Edit: May 7th, 2009, 4:03pm by Hippo » |
IP Logged |
|
|
|
cryptogrammer
Newbie
Posts: 3
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #4 on: Jun 7th, 2009, 2:27am » |
Quote Modify
|
Hi,
can anyone explain what exacly this nth sum problem is, i tried searching for it on the forum but didnt find any.
thanks.
|
|
IP Logged |
|
|
|
cryptogrammer
Newbie
Posts: 3
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #5 on: Jun 7th, 2009, 2:43am » |
Quote Modify
|
Ah i am sorry, problem was there just two entries below.
sorry for the trouble 
|
|
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #6 on: Mar 26th, 2010, 1:47pm » |
Quote Modify
|
on May 7th, 2009, 3:37pm, Hippo wrote:Hmmm. Noone interested. May be the running time I can achieve O(k\sqrtn logkn). Actually looking from m-th sum for rather small m O(k\sqrtm logkn). With this hint the solution is rather straightforward...
And for m\in \Omega(n2/log n) O(n log m*logk-2n) modification works |
|
Please explain.
Also,i couldn't understand the nlogn solution given here
[url]The largest value will be (A[0],B[0]).
Given the M largest values, the M+1st largest value will be a (4-connected) neighbour of one of the larger values. So use a balanced binary tree initialized with just (A[0], B[0]), then repeatedly extract the pair with the largest value, and insert the two neighbours (except when duplicate).
There will always be at most two new neighbours, so the size of the BBT is at most 2n (and in fact generally much less)[/url]
Someone please help me understand this problem. I could only get n^2logn solution which is quite bad.
I am trying to proceed towards getting maximum bound of two arrays where kth largest sum is possible,by doing some some search based on sqrt(k) as the min bound on both arrays together. But i am completely struck 
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #7 on: Aug 10th, 2010, 4:25pm » |
Quote Modify
|
So hint/almost solution: At least how many sums are less than
A1i1+A2i2+...+Akik
Suppose arrays are sorted in increasing order.
Try to devide index space of possible n minimal sums into as small intervals as possible.
Test chosen pivot value by binary search in each interval and summing less and higher parts togther to complete the test. ... log n times the number of intervals time is sufficient.
Weighted median as pivot guarantees the total size of intervals is reduced by 1/4 each iteration so at most log number of iterations is required.
So number of intervals times log^2 is sufficient time.
|
| « Last Edit: Aug 10th, 2010, 4:26pm by Hippo » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #8 on: Oct 5th, 2010, 6:36am » |
Quote Modify
|
on Aug 10th, 2010, 4:25pm, Hippo wrote:So hint/almost solution: At least how many sums are less than
A1i1+A2i2+...+Akik
Suppose arrays are sorted in increasing order.
Try to devide index space of possible n minimal sums into as small intervals as possible.
Test chosen pivot value by binary search in each interval and summing less and higher parts togther to complete the test. ... log n times the number of intervals time is sufficient.
Weighted median as pivot guarantees the total size of intervals is reduced by 1/4 each iteration so at most log number of iterations is required.
So number of intervals times log^2 is sufficient time. |
|
Can you explain this in more detail ? :|
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Find n-th sum of constant number of sorted arr
« Reply #9 on: Oct 15th, 2010, 6:50am » |
Quote Modify
|
For simplicity, let's take Bij = Aij - Ai1. If you solve the problem with the Bij you just need to add sum(Ai1) to get the result for the Aij.
For k=1, the sum is
sum(Bi[1]) = 0
For k=2, you need to substitute one term Bi[1] with Bi[2]. Choose j with the smallest difference Bi[2].
The 2nd smallest sum is the smallest Bi[2].
For k=3, you have to consider 2 cases:
a. substitute one Bi[1] with the corresponding Bi[3]
b. substitute two of the Bi[1] with the corresponding Bi[2].
In case a. the best sum is the smallest Bi[3].
In case b. the best sum is the sum of the 2 smallest Bi[2].
For k=4, the cases to consider are (we'll ignore the Bi[1]s which are zero anyway):
a. one Bi[4]
b. sum of three different Bi[1]
c. one Bi[2] and one Bj[3] (i<>j)
The best sum in a. is the smallest Bi[4].
The best sum in b. is the sum of the 3 smallest Bi[2].
For case c. it would be the smallest Bi[2] + the smallest Bi[3], except that if they happend for the same i, you must try the second best of the one or the other.
You can give all these answers after identifying the 3 smallest Bi[1], the 2 smallest Bi[2] and the smallest Bi[3]. And these can be found in O(n).
Sorry if it is not very clearly explained.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print