simp1eton's blog

By simp1eton, 11 years ago, In English
Hi, can someone give me some hints about this problem? Thanks!

http://www.z-training.net/tasks.php?show_task=5000000584
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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?
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.