Re: [algogeeks] Pairwise Sum Array
I think the output is wrong. It should be
1 3 4 9 n in no call them ai's a[1] to a[n]
4 5 10 7 12 13 m in no call them bi's b[1] to b[m]
I assume starting from 1 to make manipulation easier
n(n-1)/2= m
n(n-1)=2m
n2 -n -2m=0
using quadratic formula:-
n=1 + sqrt( 1+8m)/2
This will always be a whole no if it isnt then error.
Once I know n then what remains is algebraic manipulation. fill in the
following matrix :-
a1+a2 a1+a3 ... a1+an = b1 .. bn NOTE! n not m
a2+a3 .. a2+an = b(n+1)..b(2n)
an-1+an=bm
12 13 1n
23 2n
(n-1)n
1st ALL C[i][j]=0; i : 1 to n-1 and j : 2 to n
offset=0
Then
for( i=1; i=(n-1) ; i++)
for( j=i+1; j=n ; j++) {
C[i][j] = b[ offset + j - 1 ] ;
}
offset= offset+j-1;
}
for( i=1; i=(n-1) ; i++)
for( j=i+1; j=n ; j++) {
D[i][j] = C[i][j] - C[i+1][j];
}
}
now C[i][j] = a[i] + a[j]
D[i][j+1] = a[i]-a[j]
We may solve for the a[i]'s.
( see rough figure below)
Subtract R i+1 from R i
a1+a2 (a1-a2) ... a1-a2 = RHS
a2+a3 ...a2-a3 = RHS
an-2+an-1 an-2-an-1 =RHS
an-1+an=RHS
I am in a hurry as I have to go home now, sorry, but I think people will see
the solution. Is there a better way?
Ashim.
On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan
radhakrishnance...@gmail.com wrote:
This s a topcoder problem :)
On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote:
If pairwise sums of 'n' numbers are given in non-decreasing order
identify the individual numbers. If the sum is corrupted print -1
Example:
i/p:
4 5 7 10 12 13
o/p:
1 3 4 9
Thanks Regards
Shashank
--
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.
--
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] Pairwise Sum Array
That is exactly what my solution is doing. On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: There must be another good solution..please let me know . Thanks On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think.. As like no are a,b,c,d,e so sum will be a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e; so maximuum value will be d+e which is last element of array given take last three value 1.c+d 2.c+e 3.d+e eq(1)-eq(2)=d-e; solving it with 3rd eq will give d and e and with these value we can get other values On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan radhakrishnance...@gmail.com wrote: This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- 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. -- 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.
Re: [algogeeks] Pairwise Sum Array
I think.. As like no are a,b,c,d,e so sum will be a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e; so maximuum value will be d+e which is last element of array given take last three value 1.c+d 2.c+e 3.d+e eq(1)-eq(2)=d-e; solving it with 3rd eq will give d and e and with these value we can get other values On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan radhakrishnance...@gmail.com wrote: This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- 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. -- 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] Pairwise Sum Array
There must be another good solution..please let me know . Thanks On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think.. As like no are a,b,c,d,e so sum will be a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e; so maximuum value will be d+e which is last element of array given take last three value 1.c+d 2.c+e 3.d+e eq(1)-eq(2)=d-e; solving it with 3rd eq will give d and e and with these value we can get other values On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan radhakrishnance...@gmail.com wrote: This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- 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. -- 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] Pairwise Sum Array
Last three values could be: 1.b+e 2.c+e 3.d+e On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think.. As like no are a,b,c,d,e so sum will be a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e; so maximuum value will be d+e which is last element of array given take last three value 1.c+d 2.c+e 3.d+e eq(1)-eq(2)=d-e; solving it with 3rd eq will give d and e and with these value we can get other values On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan radhakrishnance...@gmail.com wrote: This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- 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. -- 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] Pairwise Sum Array
If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- 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] Pairwise Sum Array
This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- 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] pairwise sum
If pairwise sums of ‘n’ numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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.
