Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

subbu988's blog

By subbu988, 2 months 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?

Read more »

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

By subbu988, history, 3 months ago, In English

I am trying to solve a SegTree Problem, I've written an O(N,lgN) segment tree solution using segment tree. With the given constraints I see that this approach passes For example the solution here passes the problem. I've seen that the verdict of this problem differed from TLE to AC considering memset() for each test case, usage of printf, scanf vs cin/cout and \n instead of endl. I couldn't differentiate between these two solutions and the reason the latter passes and the former results in TLE. Can someone help with this?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it