I have a solution.I cant prove the correctness but by intuition I can
conclude.This is O(1) solution.
As we have 3 sorted arrays A,B,C.So only first and last element of these 3
lists will be contributing for min/max tuple.Rest elements will be varying
from that max to min.
Suppose a={-1,-1,0}
b={-1,3,7,8,10}
c={0,1,2,3,4,5}
so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all
possible 8 tuples.In this case its for (x,y,z)=(-1,-1,0) giving a tuple 1
[max(-2,-1,1)] and so on.
Find minimum of these tuples i.e. 1.That will be the answer.Solution if O(8)
equilvalent to O(1).Please provide counter if you can find.
On Mon, Dec 20, 2010 at 11:43 AM, yq Zhang <[email protected]> wrote:
> ok. Suppose you have 3 pointers i, j, k point to the element in A, B, C
> respectively. Initialize i = j =k = 0.
> for each step, you will compare A[i], B[j], C[k].
> if A[i] is the smallest, i++
> if B[j] is the smallest, j++
> if C[k] is the smallest, k++
> (this assumes numbers in A,B,C are unique, you should be able to eliminate
> this restriction by changing above logic a little bit.)
>
> for each step compute the current triple distance and keep the minimum.
>
> Thanks
>
>
>
> On Sun, Dec 19, 2010 at 9:51 PM, Saurabh Koar <[email protected]>wrote:
>
>> @yq: Heyy yq..I m not interested in what is equivalent to what and
>> what is not not equivalent to what..I m interested to a specific
>> optimized algorithm for the specific problem stated above.If u can
>> figure out equivalence u can also devise the algorithm for the above
>> problem.Nw would u please state that??or provide any link??
>>
>> --
>> 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]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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?hl=en.
