Re: [algogeeks] Re: Find Max Sum Value Pairs
how to do it DP way? Anyone with code?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, Sep 3, 2011 at 9:00 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Try your code with
n = 10
a[10] = {11,22,33,44,55,66,77,88,99,110}
b[10] = {10,20,30,40,50,60,70,80,90,100}
Your code gets
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(88, 100) = 188
(110, 70) = 180
(77, 100) = 177
(110, 60) = 170
(66, 100) = 166
(110, 50) = 160
but it should get
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(99, 90) = 189
(88, 100) = 188
(110, 70) = 180
(99, 80) = 179
(88, 90) = 178
(77, 100) = 177
It fails because, after choosing the first four pairs, it does not
consider all three candidates, (110, 70) = 180, (99, 90) = 189, and
(88, 100) = 188. It only looks at the first and last of these. Later
on, it fails to consider (99, 80) = 179 and (88, 90) = 178.
After you have chosen the maximum pair, every unused pair that is the
last unused pair in both its row and column of the (implicit) n by n
matrix of pairwise sums is a candidate. When you have chosen n-1
pairs, there can be O(sqrt(n)) candidates for the last choice. You are
considering only two of them.
Dave
On Sep 2, 3:09 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
if I have understood the question correctly then:
a[n-1] + b[i] a[j] + b[i] for all 0 = j n-1
and a[j] + b[n-1] a[j] + b[i] for all 0 = i n-1
therefore,
i = j =n-1;
count = 1;
S[0] -- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]
while(count n){
if(p q){
j--;
S[count++] -- (a[n-1], b[j]);
}else{
i--;
S[count++] -- (a[i], b[n-1]);
}
p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];
}
Time complexity: O(n) : http://ideone.com/FXfVj
On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank shashank7andr...@gmail.com
wrote:
@Dave Correct , Missed to Provide the Correct Time Complexity in Worst
Case
it Will be O(N^2) , as we need to find out n such maximum pair , will
think
about O(N0) Algo, if able to do it, will post the Algo here
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
@Piyush: Try your code with
n = 10
a[10] = {11,22,33,44,55,66,77,88,99,110}
b[10] = {10,20,30,40,50,60,70,80,90,100}
Your code gets
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(88, 100) = 188
(110, 70) = 180
(77, 100) = 177
(110, 60) = 170
(66, 100) = 166
(110, 50) = 160
but it should get
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(99, 90) = 189
(88, 100) = 188
(110, 70) = 180
(99, 80) = 179
(88, 90) = 178
(77, 100) = 177
It fails because, after choosing the first four pairs, it does not
consider all three candidates, (110, 70) = 180, (99, 90) = 189, and
(88, 100) = 188. It only looks at the first and last of these. Later
on, it fails to consider (99, 80) = 179 and (88, 90) = 178.
After you have chosen the maximum pair, every unused pair that is the
last unused pair in both its row and column of the (implicit) n by n
matrix of pairwise sums is a candidate. When you have chosen n-1
pairs, there can be O(sqrt(n)) candidates for the last choice. You are
considering only two of them.
Dave
On Sep 2, 3:09 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
if I have understood the question correctly then:
a[n-1] + b[i] a[j] + b[i] for all 0 = j n-1
and a[j] + b[n-1] a[j] + b[i] for all 0 = i n-1
therefore,
i = j =n-1;
count = 1;
S[0] -- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]
while(count n){
if(p q){
j--;
S[count++] -- (a[n-1], b[j]);
}else{
i--;
S[count++] -- (a[i], b[n-1]);
}
p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];
}
Time complexity: O(n) : http://ideone.com/FXfVj
On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank
shashank7andr...@gmail.comwrote:
@Dave Correct , Missed to Provide the Correct Time Complexity in Worst Case
it Will be O(N^2) , as we need to find out n such maximum pair , will think
about O(N0) Algo, if able to do it, will post the Algo here
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Sum Value Pairs
@Dave..:-O well catch...
On Sat, Sep 3, 2011 at 9:00 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Try your code with
n = 10
a[10] = {11,22,33,44,55,66,77,88,99,110}
b[10] = {10,20,30,40,50,60,70,80,90,100}
Your code gets
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(88, 100) = 188
(110, 70) = 180
(77, 100) = 177
(110, 60) = 170
(66, 100) = 166
(110, 50) = 160
but it should get
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(99, 90) = 189
(88, 100) = 188
(110, 70) = 180
(99, 80) = 179
(88, 90) = 178
(77, 100) = 177
It fails because, after choosing the first four pairs, it does not
consider all three candidates, (110, 70) = 180, (99, 90) = 189, and
(88, 100) = 188. It only looks at the first and last of these. Later
on, it fails to consider (99, 80) = 179 and (88, 90) = 178.
After you have chosen the maximum pair, every unused pair that is the
last unused pair in both its row and column of the (implicit) n by n
matrix of pairwise sums is a candidate. When you have chosen n-1
pairs, there can be O(sqrt(n)) candidates for the last choice. You are
considering only two of them.
Dave
On Sep 2, 3:09 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
if I have understood the question correctly then:
a[n-1] + b[i] a[j] + b[i] for all 0 = j n-1
and a[j] + b[n-1] a[j] + b[i] for all 0 = i n-1
therefore,
i = j =n-1;
count = 1;
S[0] -- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]
while(count n){
if(p q){
j--;
S[count++] -- (a[n-1], b[j]);
}else{
i--;
S[count++] -- (a[i], b[n-1]);
}
p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];
}
Time complexity: O(n) : http://ideone.com/FXfVj
On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank shashank7andr...@gmail.com
wrote:
@Dave Correct , Missed to Provide the Correct Time Complexity in Worst
Case
it Will be O(N^2) , as we need to find out n such maximum pair , will
think
about O(N0) Algo, if able to do it, will post the Algo here
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
@Shashank: Without looking over your algorithm in detail, let me just say that it solves a different problem than the one asked by the original poster. You are finding the kth maximum sum, but the problem asks to find all of the first n maximum sums. So you would have to apply your algorithm n times. The total complexity for the original problem would be O(n^2). Dave On Sep 2, 5:18 am, WgpShashank shashank7andr...@gmail.com wrote: Yes I Think Its Obviously O(N) Algorithm :P Here is Approach Algorithm: Take 0th index value from 1st array 1st index value from 2nd array store it in S1 Now 0th index value from 2nd array 1st index value from 1st array , store in S2 Also stores starting ending index of each array -take care-off initialize maxsum variable to a[0]+b[0] Keep checking until we found kth sum from array a b where a is from 1st b is from if s1s2 then increment array b lastindex until its equal to length of this array update maxsum=s1 else then increment array a last-index until its equal to length of this array maxsum=s2; Finally Return maxsum; Here is More infohttp://shashank7s.blogspot.com/2011/08/find-kth-largest-sumab-possibl... Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
@Dave Correct , Missed to Provide the Correct Time Complexity in Worst Case it Will be O(N^2) , as we need to find out n such maximum pair , will think about O(N0) Algo, if able to do it, will post the Algo here Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Sum Value Pairs
if I have understood the question correctly then:
a[n-1] + b[i] a[j] + b[i] for all 0 = j n-1
and a[j] + b[n-1] a[j] + b[i] for all 0 = i n-1
therefore,
i = j =n-1;
count = 1;
S[0] -- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]
while(count n){
if(p q){
j--;
S[count++] -- (a[n-1], b[j]);
}else{
i--;
S[count++] -- (a[i], b[n-1]);
}
p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];
}
Time complexity: O(n) : http://ideone.com/FXfVj
On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank shashank7andr...@gmail.comwrote:
@Dave Correct , Missed to Provide the Correct Time Complexity in Worst Case
it Will be O(N^2) , as we need to find out n such maximum pair , will think
about O(N0) Algo, if able to do it, will post the Algo here
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Sum Value Pairs
@pitush: pls explain your logic once
On Fri, Sep 2, 2011 at 4:09 PM, Piyush Grover piyush4u.iit...@gmail.comwrote:
if I have understood the question correctly then:
a[n-1] + b[i] a[j] + b[i] for all 0 = j n-1
and a[j] + b[n-1] a[j] + b[i] for all 0 = i n-1
therefore,
i = j =n-1;
count = 1;
S[0] -- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]
while(count n){
if(p q){
j--;
S[count++] -- (a[n-1], b[j]);
}else{
i--;
S[count++] -- (a[i], b[n-1]);
}
p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];
}
Time complexity: O(n) : http://ideone.com/FXfVj
On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank
shashank7andr...@gmail.comwrote:
@Dave Correct , Missed to Provide the Correct Time Complexity in Worst
Case it Will be O(N^2) , as we need to find out n such maximum pair , will
think about O(N0) Algo, if able to do it, will post the Algo here
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Sum Value Pairs
yeah piyush's solution seems correct to me... if current amx is from a[i],b[j], then next maximum can only be either of a[i-1],b[j] or a[i],b[j-1] continue!!! -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Sum Value Pairs
Since A(n) and B(n) are sorted so in the pair (a[i], b[j]) either i = n-1 or j = n-1 or both. 1.) so the first element is (a[n-1], b[n-1]) 2.) now, we have two numbers to compare p = a[n-1]+ b[n-2] and q = a[n-2]+b[n-1] 3.) if pq then p = a[n-1]+b[n-3] else q = a[n-3] + b[n-1] and repeat in the similar fashion The point to note is, either a's index is n-1 or b's index is n-1. On Sat, Sep 3, 2011 at 10:18 AM, Siddhartha Banerjee thefourrup...@gmail.com wrote: yeah piyush's solution seems correct to me... if current amx is from a[i],b[j], then next maximum can only be either of a[i-1],b[j] or a[i],b[j-1] continue!!! -- 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 algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
My guess is O(n) time bound can only be achieved with Dynamic
Programming here. Though, still to get proper sub problems to solve.
Calling out to Dynamic Programming experts to crack this one.
On Sep 1, 4:25 pm, bharatkumar bagana bagana.bharatku...@gmail.com
wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning) elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
thanks
--mac
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
Start with pair (A(i), B(j)) where i and j are both n.
Then the next largest pair will either be (A(i-1), B(n)) or (A(n),
B(j-1)). Whichever sum is larger, set i and j to those values. Repeat
as desired.
Don
On Sep 1, 3:45 am, Navneet Gupta navneetn...@gmail.com wrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
@Don: It is more complicated than that.
1st pair: (A(n),B(n)).
2nd pair: Either (A(n-1),B(n)) or (A(n),B(n-1)).
Suppose the 2nd pair is (A(n-1),B(n)).
3rd pair: Either (A(n-2),B(n)) or (A(n),B(n-1)).
Suppose the 3rd pair is (A(n),B(n-1)).
4th pair: Can be any of (A(n-2),B(n)), (A(n-1),B(n-1)), and
(A(n),B(n-2)).
Every unused pair that is the first unused pair in both its row and
column is eligible. When you have chosen n-1 pairs, there can be
O(sqrt(n)) candidates for the last choice. To me, this says that you
must keep the eligible candidates in some data structure. To choose a
pair, you must search the data structure for the largest sum. When you
have chosen a pair, you must update the data structure to remove the
chosen pair, check each of the two neighbors to see if it already in
the data structure, and add any not already in the structure to the
structure. Doing all of this n times with O(n) work seems unlikely to
me. I hypothesize that the best you can do it in is O(n log n). I
think a balanced binary search tree might be appropriate, since each
of these operations can be performed in O(log(size of tree)).
I'd love for someone to prove me wrong by demonstrating an O(n)
solution.
Dave
On Sep 1, 9:55 am, Don dondod...@gmail.com wrote:
Start with pair (A(i), B(j)) where i and j are both n.
Then the next largest pair will either be (A(i-1), B(n)) or (A(n),
B(j-1)). Whichever sum is larger, set i and j to those values. Repeat
as desired.
Don
On Sep 1, 3:45 am, Navneet Gupta navneetn...@gmail.com wrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning) elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
thanks
--mac
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
i kinda just ate my own words there ;P if a set has unique
elements, {4,4} isnt possible.. it would just be {4}
i'm not sure how to deal with ( ) instead of { }
On Sep 1, 5:12 pm, icy` vipe...@gmail.com wrote:
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning) elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
thanks
--mac
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
@Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
(1,2). These are different than the pairs you listed, because they are
ordered: the first element is from set A and the second element is
from set B. This was masked because of your choice of A = B. But you
wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
= [5 6 7 8].
There is no restriction in the original problem statement that the
numbers in each array are distinct. One application I have seen of
this problem is with the travel reservation web sites, where they will
show you some number of the cheapest round trip flight combinations.
In that case, there is more to the data items than just the price,
including at least airline and flight time. Several different flights
might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
[1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
case, the first 2 (cheapest) round trips will have score 2. Then
follows 7 round trips with score 3. Etc.
Dave
On Sep 1, 4:12 pm, icy` vipe...@gmail.com wrote:
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning) elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
thanks
--mac
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Max Sum Value Pairs
@Dave thanks for clarifying that (4,3) is different from (3,4)
But let's suppose, for example, n is 3
so A is of size n, and B is of size n, as required
e.g. A = [1 1 2] , B = [1 2 2]
S = { (1,1) (1,2) (1,2) (1,1) (1,2) (1,2) (2,1) (2,2) (2,2) }
but now you see there are repeated points that are also in the same
order. These are duplicates and should be removed, if S is truly a
set. Pruned version:
S = { (1,1) (1,2) (2,1) (2,2) }
size of set is not n^2, or 9, but rather
(size of unique(A) ) * (size of unique(B) ) = 4
With this in mind, I would first eliminate or ignore duplicates as you
are iterating through A, B
On Sep 1, 5:50 pm, Dave dave_and_da...@juno.com wrote:
@Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
(1,2). These are different than the pairs you listed, because they are
ordered: the first element is from set A and the second element is
from set B. This was masked because of your choice of A = B. But you
wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
= [5 6 7 8].
There is no restriction in the original problem statement that the
numbers in each array are distinct. One application I have seen of
this problem is with the travel reservation web sites, where they will
show you some number of the cheapest round trip flight combinations.
In that case, there is more to the data items than just the price,
including at least airline and flight time. Several different flights
might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
[1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
case, the first 2 (cheapest) round trips will have score 2. Then
follows 7 round trips with score 3. Etc.
Dave
On Sep 1, 4:12 pm, icy` vipe...@gmail.com wrote:
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning)
elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
thanks
--mac
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
[algogeeks] Re: Find Max Sum Value Pairs
Okay, I guess this question will be more tough to tackle in complete
generality. in two sorted arrays, lets assume elements are in strictly
increasing order, hence the extra care of duplicates in either array
is gone. However, the same element can be present in both arrays.
For ex.
{1,2,3} {2,3,4}
The duplicate case can obviously be solved, but i am not sure if we
can have O(n) time bound in that case.
On Sep 2, 3:36 am, icy` vipe...@gmail.com wrote:
@Dave thanks for clarifying that (4,3) is different from (3,4)
But let's suppose, for example, n is 3
so A is of size n, and B is of size n, as required
e.g. A = [1 1 2] , B = [1 2 2]
S = { (1,1) (1,2) (1,2) (1,1) (1,2) (1,2) (2,1) (2,2) (2,2) }
but now you see there are repeated points that are also in the same
order. These are duplicates and should be removed, if S is truly a
set. Pruned version:
S = { (1,1) (1,2) (2,1) (2,2) }
size of set is not n^2, or 9, but rather
(size of unique(A) ) * (size of unique(B) ) = 4
With this in mind, I would first eliminate or ignore duplicates as you
are iterating through A, B
On Sep 1, 5:50 pm, Dave dave_and_da...@juno.com wrote:
@Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
(1,2). These are different than the pairs you listed, because they are
ordered: the first element is from set A and the second element is
from set B. This was masked because of your choice of A = B. But you
wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
= [5 6 7 8].
There is no restriction in the original problem statement that the
numbers in each array are distinct. One application I have seen of
this problem is with the travel reservation web sites, where they will
show you some number of the cheapest round trip flight combinations.
In that case, there is more to the data items than just the price,
including at least airline and flight time. Several different flights
might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
[1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
case, the first 2 (cheapest) round trips will have score 2. Then
follows 7 round trips with score 3. Etc.
Dave
On Sep 1, 4:12 pm, icy` vipe...@gmail.com wrote:
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning)
elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
in S. The value of such a pair is defined as Val(a,b) = a + b. Now
we
want to get the n pairs from S with largest values. need an O(n)
algorithm.
--
Regards,
Navneet
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
thanks
--mac
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
