0
$\begingroup$

Good day.

Consider N points forming a circle (N is even and is between 1 and 200).

The task is to calculate the minimum cost of linking all 2 points (as pairs) without any lines intersecting.

Each point is given an ID. The cost to link 2 points a and b is (id(a)+id(b))²

Please note: a point can't be part of 2 pairs.

Example: N=4

a=1, b=2, c=1, d=2

Cost=18

Here's how I approached the problem:

First we locate the point with the smallest id and the node with the greatest id value. If one is odd and the other is even then we link them. Else, we locate the point with the second biggest id value and we link the located points.

The cost is calculated and saved, and the points are removed from our structure (C++ std::list for example) and the function is called recursively twice, each time with a subset of the current circle, left part and right part (2 new circles)

The base case for the recursive function is returning the square of the sum of 2 points if N=2

Thank you.

$\endgroup$
  • 3
    $\begingroup$ Welcome to the site! What did you try? Where did you get stuck? This is, as I recall, a fairly standard exercise and the point of such exercises is to get you thinking about the concepts. We're happy to help with the concepts but just solving the exercise for you is unlikely to really help. $\endgroup$ – David Richerby Feb 5 '17 at 13:26
  • $\begingroup$ Thank you. My problem is that I don't have any good examples to compare my idea with. I will edit my post and add how I approached the problem. $\endgroup$ – StrayPointer Feb 5 '17 at 15:46
  • $\begingroup$ Your recursion looks good, but I think you might not get the minimum cost. It makes sense to try dynamic programming here. Also it's very unusual to use the word ID for your points - it's actually their weight, right? $\endgroup$ – HEKTO Feb 6 '17 at 19:20
  • $\begingroup$ @HEKTO I'm not sure about that. If I'm not mistaken the term "weight" refers to the weight of an edge between 2 vertices in a graph. I used the terminology presented in the task and ID refers to the vertex value itself. $\endgroup$ – StrayPointer Feb 6 '17 at 19:28
  • $\begingroup$ The ID is normally what identifies an object, and it's usually unique. Your ids are not unique. People use weight or cost or price to talk about some quantitative property of the object, which might participate in summation $\endgroup$ – HEKTO Feb 6 '17 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.