subbu988's blog

By subbu988, 3 years ago, In English

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

After sorting.,

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There should be a pair of trees at both ends of the road. With your tree arrangement, there are no trees at the $$$x = 10$$$ end of the road.

To fix your arrangement, the tree at $$$(6, 0)$$$ should instead be moved to $$$(10, 1)$$$, while the tree at $$$(9, 0)$$$ should be moved to $$$(10, 0)$$$.