I am trying to solve this problem: http://acm.tju.edu.cn/toj/showp2886.html
I have tried a few solutions, I will explain 2 of them. Note that both assume that cost(position) is a convex function, which means that it decreases towards the middle (in fact its somewhere towards median(supply points)), and the graph looks more or less like an U shape.
Finding the leftmost and rightmost supply point position that has cost(position) <= M. After I find the minimum and maximum, I try to see if I can make the interval a little larger (since the restaurant doesn't have to be places exactly on a supply point). This is a good solution but takes very much to compute the last bit. It fails on the tests where M is very large and there exists few supply points with minimum cost. Complexity: O(NlogN) + O(M). This solution below as it is gets Time Limit Exceeded, but I have tried another one where I compute in O(1) how much can I go in both directions and I get Wrong Answer.
Since the function is convex I can use a ternary search to find the minimum value. If the minimum is less than M, I then binary search the lower and the upper bound (meaning M) of the function. Complexity: O(NlogM) since for every O(logM) I compute the cost in O(N).
This is what I've tried and I still get "Wrong Answer", so I need some help since this is driving me nuts.
The problem is not really clear in specifications (or at least I think so) because when I first read it I didn't think the cost was computed from all supply points, but just from the nearest. The example cleared that out. Also, I don't know if my assumption of cost(position) function being convex is really true. But I've tried many examples and it seems so.
Thanks. Any help is appreciated. :D
The minimum objective value in between two consecutive supplier locations in the list must occur at one of the two supplier locations. To see this, consider two supplier locations with no supplier locations in between, whose locations differ by more than 1. Suppose the left hand supplier location gives less than or equal objective value than the right hand supplier location. Then each time you move 1 step to the right starting at the left hand supplier location, the objective function goes up (weakly, it may stay constant) because the objective function changes by the same amount as you move to the right by 1 step at a time in between the two consecutive supplier locations. Thus the only thing you need to compute is how many supplier locations give the same global minimum. These will occur in consecutive segments (endpoints given by supplier locations), and all locations in between the endpoints of each segment will also give the same global minimum.
Note that it may be possible, according to my analysis, to have two non-consecutive segments that give the same global minimum objective value. If so, then your function may not be convex and this may be the source of your difficulties in your current attempts.
Calculating the objective value at each supplier location can be done in O(N) time for N suppliers by processing from left to right.