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 <
[email protected]> wrote:
> This s a topcoder problem :)
>
> On Wed, Feb 23, 2011 at 7:16 PM, bittu <[email protected]> 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 [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.
> >
> >
>
> --
> 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.
>
>
--
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.
