-----------------------------------

coolgod

Wed Feb 09, 2011 11:35 pm


line search?

-----------------------------------

I was doing this usaco contest question which I was told it involved line searching.
the wikipedia article confused me.
Problem 2: Soda Machine 
If i understood line searching correctly, I basically skipped it with the c++ lower_bound method.
My program ran over the time.
I would like to learn more about this line search or techniques to do this question.
Any help?


-----------------------------------

Tony

Thu Feb 10, 2011 2:38 am


RE:line search?

-----------------------------------

The location of the machine will be at the right-side of some cow's edge (or left, by symmetry). If there exists a max answer such that it is not at the right-most edge of any cow, then the location can be moved one unit to the right, without putting it out of any cow's range. Thus, by induction, it could be moved to the right-sided edge of some cow.

This should get you going in the right direction of thought.

I propose an O(NlogN) solution, for N ~= 50,000