I am trying to solve this problem. I am having trouble understanding the sample IO.
The abridged statement is, Given an array of integers (x coordinates ) representing the position of trees on the left side of the road, and the width of the road, calculate the minimum Euclidean distance such that the trees are parallel on the left and right side of the road.
For the second test case,
6 10 1 0 9 3 5 5 6
Tree points : [0,3,5,5,6,9]
I am calculating Euclidean distance as follows,
[I am assuming y coordinates for trees on the left side as 0 and that of the right side are the width of the road. Is that a mistake?]
The first coordinate is (0,0). I can move the tree from (3,0) to (0,1) [Euclidean Distance = 3.162278] The third coordinate is (5,0). I can move the other tree from (5,0) to (5,1) [Euclidean Distance = 1] The fifth coordinate is (6,0). I can move the other tree from (9,0) to (6,1) [Euclidean Distance = 3.162278]
So the total cost is 7.32456. But the minimum result is 9.285.
Where am I getting it wrong?
Edit : I understand this greedy approach may not always give correct results. But can someone help me understand why this isn't a valid arrangement and what arrangement gives the result as in the sample IO?