Ajinkya. It would be great if you provided us with compilable version of your solution. The program that can be found by the link you have posted before doesn't work.
Implementation of my idea can be found here: http://programming-challenges.googlegroups.com/web/Find_nums_by_sums.cpp But as I've mentioned before it is not the best one as it checks all subsets of sequence of size n - 1. :( On Nov 8, 4:58 am, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote: > On 11/7/07, 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? > > Though the order is not imp you cant tell which 2 variables for a particular > equation. > > 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... > > -- > Ciao, > Ajinkya --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
