you are right!!!
but i think there is a interesting thing hided in this problem.
let set[i] = {a[i]+b[1], a[i]+b[2], a[i]+b[3], ..., ai+an},
and MAX is the set of n largest numbers. if there
are some elements in the set[i] belong to the MAX,
we can know the number of these elements must be
less than n/(n-i+1) because there are at least the
same number of elements, seperately in the set[i+1],
the set[i+2], ..., and the set[n], also belong to the MAX.
concretely, there are at most n/(n-i+1) consecutive
elements start from a[i]+b[n-n/(n-i+1)+1] to a[i]+b[n]
in the set[i] belong to the MAX.
so we can just consider n+n/2+n/3+...+1 elements
like illustration below, where n=8.
set[1] X X X X X X X O 8/8
set[2] X X X X X X X O 8/7
set[3] X X X X X X X O 8/6
set[4] X X X X X X X O 8/5
set[5] X X X X X X O O 8/4
set[6] X X X X X O O O 8/3
set[7] X X X X O O O O 8/2
set[8] O O O O O O O O 8/1
1 2 3 4 5 6 7 8
(O represents considered elements, X reprensents
irrespective elements)
now we can construct a new ALGO to sovle this problem.
1) create a array of n size (named mini[n]), it will records
the index of the first element in every set (say set[i]) just
inludes considered elements.
2) let mini[n] equals 1, it means considering n elements
in the set[n]
3) let mini[i] equals n-n/(n-i+1)+1, it means considering
n/(n-i+1) elements in the set[i]
4) find the minimum from a[i]+b[mini[i]], a[i+1]+b[mini[i+1]],
a[i+2]+b[mini[i+2]], ..., a[n]+b[mini[n]].
5) if a[j]+b[min[j]] is the minimum, then let mini[j] = mini[j] ++.
if hasn't looped n/(n-i+1) times, then go to 4).
6) if hasn't looped n-1 times, then go to 3).
the total time cost is n/2+2n/3+3n/4+...+(n-1)n/n
= n(n-(1/2+1/3+1/4+...+1/n))
sorry, i can't remeber the result of (1/2+1/3+..+1/n)
but, i think in the step 4) and the step 5), can do some
optimizations.
a simple example:
a[] = {1,3,15,16}
b[] = {22,24,26,28}
23 25 27 29
25 27 29 31
37 39 41 43
38 40 42 44
set[1] X X X 29
set[2] X X X 31
set[3] X X 41 43
set[4] 38 40 42 44
mini = {0,0,0,1}
i=3
mini = {0,0,3,1}
set[3] X X 41 43
set[4] X 40 42 44
mini = {0,0,3,2}
set[3] X X 41 43
set[4] X X 42 44
mini = {0,0,3,3}
i=2
mini = {0,4,3,3}
set[2] X X X 31
set[3] X X 41 43
set[4] X X 42 44
mini = {0,0,3,3}
set[2] X X X X
set[3] X X 41 43
set[4] X X 42 44
i=1
mini = {4,0,3,3}
set[2] X X X 29
set[2] X X X X
set[3] X X 41 43
set[4] X X 42 44
mini = {0,0,3,3}
set[2] X X X X
set[2] X X X X
set[3] X X 41 43
set[4] X X 42 44
aamir wrote:
> Hi rainix,
>
> I feel that this solution is not correct.
>
> if a[i] + b[j] < a[i-1]+b[n]
> we decrease i;
> this means that the previous a[i] is never considered again with any
> other elements of B. It should be considered again because the
> a[i-1]+b[n] is being decreased continuously.
>
> Please correct me if i am wrong.
>
>
>
> > i think this ALGO can resovle the problem
> >
> > 1) do comparison from a[n]+b[n] because it is the largest number in
> > the new set;
> > 2) can think those numbers, including a[i]+b[n], a[i]+b[n-1],
> > a[i]+b[n-2], ... untill a[i]+b[j]<a[i-1]+b[n] (where 0<i<=n, 0<=j<=n),
> > are a part of n largest numbers in the new set;
> > 3) if a[i]+b[j]<a[i-1]+b[n] and i > 0, then let i = i-1, and
> > recursively do the step 2); else
> > 4) if a[i]+b[j]<a[i-1]+b[n] and i = 0 and do not find all n largest
> > numbers, then find the remained largest numbers from a[1]+b[n] to
> > a[1]+b[1].
> >
> > psuedo-code:
> > find (i)
> > {
> > if (i = 0)
> > {
> > for (j=n; j>count; j--)
> > print (a[1]+b[j]);
> > return;
> > }
> >
> > for (j=n, j<=0; j--)
> > {
> > if (a[i]+b[j]<a[i-1]+b[n])
> > break;
> > print (a[i]+b[j]);
> > count ++;
> > if (count == n)
> > return;
> > }
> >
> > find(i--);
> >
> > return;
> > }
> >
> > time cost: O(n)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
