This works, but by now I am not sure it is the best way. Actually the problem is that you can have more (undesired) solutions (I have tested it in Maple). Also, it is very important to well chose what equations to put in the system. A choice on the equations can eliminate symmetry.
So, you are right when saying that the order of values matters. What I say about symmetry is only valid when you consider the whole (non square) system. I will try to gain more insight into the right way of choosing the equations, and then I will post. Thanks Ajinkya for the links! Thank you Andrey for this interesting problem! Have a nice day, Antonio On Nov 7, 10:28 pm, anvera <[EMAIL PROTECTED]> wrote: > Why not? Does order really matters here? Look at the symmetry of the > problem. Put 3,4,5,5 and then 4,5,6,7 at the right side. Look at the > solutions. How they differ? Is this natural? > > On Nov 7, 6:55 pm, Andrey <[EMAIL PROTECTED]> wrote: > > > Won't work. > > You just can't build such a system, because you don't know in which > > order values should appear in right part of system. Say, we have the > > follwing input of 6 numbers: 3, 4, 5, 5, 6, 7 and we are supposed to > > find 4 values (4 * (4 - 1) / 2 = 6) x1, x2, x3, x4 > > > What the system will look like? > > > x1 + x2 = ? > > x1 + x3 = ? > > x1 + x4 = ? > > x2 + x3 = ? > > x2 + x4 = ? > > x3 + x4 = ? > > > On 7 нояб, 20:16, anvera <[EMAIL PROTECTED]> wrote: > > > > I have not developed entirely the idea, but I am sure it works. > > > Just write the corresponding linear system. You will have n unknowns > > > and n(n-1)/2 equations. Provided that the system is consistent you can > > > find a solution by Gaussian elimination. > > > For the complexity, you can do it in less than n^3/3 +O(n^2) > > > operations, because it is simpler than just inverting a nxn matrix. > > > Inverting the matrix can let you solve the problem for many instances. > > > It would be interesting to exploit the special structure of this > > > matrix in order to speed up the computation. Please post if you find > > > such an improvement. > > > > Best Regards, > > > > Antonio > > > > On Nov 7, 5:16 pm, Andrey <[EMAIL PROTECTED]> wrote: > > > > > Any set of n integers form n(n - 1)/2 sums by adding every possible > > > > pair. > > > > The task is to find the n integers given the set of sums. > > > > > Any ideas? > > > > > I've found out the solution but I doubt it the best one... --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
