It's funny this problem. The hardest thing to determine is when to output -1; P is simply the product of smallest x elements, where x = sqrt(2*n). Note that if x * ( x + 1 ) != 2*n you must output -1, but if x * ( x + 1 ) == 2*n then you must check if the n lengths make up a valid input.

Hi,

Thanks for your reply. However, I don't really understand your algorithm, so I tested it on the example below. Please tell me if I misunderstood you anywhere.

Suppose the edges given are 1, 1, 2, 3, 4, 5. There are 6 edges, which meansand sqrt(2 * 6) = 3 (I am assuming you take the floor of the number), and 3 * (3 + 1) = 12 = 2 * 6. Therefore, there is a possibility of a valid output. Then, you multiply the x smallest elements together. In this case, it is 1 * 1 * 2 = 2. Since 1 + 1 + 2 is not equal to 5, it does not make a valid output, and therefore you output -1.

However, the answer is actually 1 * 1 * 3. One possible configuration of the points is (0,1,2,5).

Did I misunderstand you somewhere?

From what I've seen you understanded my algorithm perfectly. Also it seems that it is flawed. That's an interesting counterExample. Sorry for my mistake. It is really an interesting problem. Please let me know if you solve it.