4

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.

  1. 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.

  2. 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

epicrose
  • 175
  • 7
  • 1
    Your second approach seems correct, however, there are some small bugs in it, one thing I noticed is you should avoid using `int` for your `left` and `right`, and use `long long` instead. – Pham Trung Apr 15 '15 at 08:57
  • @PhamTrung Thanks. Tried it, still "Wrong Answer": http://pastie.org/private/fhaepmedvrxzueyxe8khaa – epicrose Apr 15 '15 at 09:11
  • I think you don't need the `middle` method also, two `upper` and `lower` methods are enough. And don't compare `m >= cost_mid`, just do a normal binary search, this comparison seems ... wrong :) – Pham Trung Apr 15 '15 at 09:13
  • @PhamTrung There can be many of the same value on consecutive positions. A normal binary search just gives me a random position that satisfies "m >= cost_mid", which doesn't help much, since I need the leftmost and the rightmost. Also, a normal binary search doesn't take into account that cost(position) is a convex function. – epicrose Apr 15 '15 at 09:56
  • Hmm, yes you are right :) , sorry, misunderstood that part – Pham Trung Apr 15 '15 at 09:59
  • Have you tried looking for cases in which your algorithm fails? What you could do is implement a brute force solution that checks if each of the `M` points is valid. Then manually input some small test cases to both of your algorithms, and see if they differ. If you catch an input they differ on, check why. – IVlad Apr 15 '15 at 12:24
  • 1
    From the original problem statement: "Total cost is the SUM [emphasis added] of the price which is the cost of food multiplied by the distance between the restaurant and its supply." Does this mean that somehow we are taking a sum, say over all supply locations, to get price? Or are we just computing price in terms of the best supply location(s) as defined by minimum (cost of food * distance)? They don't seem to make it clear whether you need all the food from all the suppliers, or just all the food from one supplier. – user2566092 Apr 15 '15 at 16:20
  • @IVlad That's what I've been doing. But I can't find an example where my solution fails. – epicrose Apr 15 '15 at 17:26
  • @user2566092 The example clarified it for me (I guess), since if it was just the minimum, the answer would be much higher. For example 0, 1 and 2 would be valid positions. – epicrose Apr 15 '15 at 17:28

1 Answers1

1

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.

user2566092
  • 4,631
  • 15
  • 20
  • Yup, this is the observation on which my first solution is based. On each position you will have some supply points on the left and right, and between 2 supply points the function increases/decreases constantly, because cost(left) will increase as it is moving away from those points, and cost(right) will decrease. Every time you get to a supply point, you move it from cost(right) to cost(left). The problem is that I cannot find an example in which there are 2 non-consecutive segments that have the same minimum. The way I see it, everything in between 2 minimum points, will be minimum. – epicrose Apr 15 '15 at 18:45
  • @epicrose Without seeing your exact code, it's hard to say whether the problem is that separated global minima can exist, or whether it's a problem with your code. My proposed solution will run very fast and be correct, even if there are separated global minima. I suggest that unless you are plagued with intellectual curiosity about the exact nature of the problem structure and solution, you implement my proposed solution as a fresh start and if it works, then it doesn't matter whether it was a bug in your old code or whether it was the fact that multiple separated global minima can exist. – user2566092 Apr 15 '15 at 18:50
  • If you look in the code (first link), the `left_sum` will always increase as the `right_sum` will decrease. So `(left_sum - right_sum)` will first be a negative number, then eventually zero, and then a positive number. This means that all the minimums will be enclosed in the part where `left_sum == right_sum`. Also, the code is exactly your suggested implementation. I also made a brute-force solution, and tried many examples, and all of them seem to follow the pattern, so I guess my only hope is to find a counter-example. – epicrose Apr 15 '15 at 18:57
  • @epicrose I will look at your code in the first link. However, I believe I have proved that my solution is correct, whereas at least in your original post you indicated that you were relying on "suspected" convexity, at least for one of the solutions, so if your code has no typos then that is the only gap I can see between your approaches and mine. – user2566092 Apr 15 '15 at 19:05
  • @epicrose Also note that my proposed solution will run in O(N) time, independent of M unless you take bit-length into account in arithmetic operations. – user2566092 Apr 15 '15 at 19:09
  • I know it can be done in O(n) (which is actually NlogN since you have to sort), I noted that. The original code did that too. You can easily find out how much the interval can be extended past the supply points. Also, the first solution I ever coded, was a variation of this one: for every supply point, if cost was <= M, computed how much it could extend to the left and to the right (taking into account other supply points), and kept the segments. At the end, took all the segments and combined them, and computed sum of end - start for every combination. Got the same results. – epicrose Apr 15 '15 at 19:26
  • I took your advice and implemented the solution again, and it seems that this time it got accepted... magically. Thanks for your effort. And for the curious who will be reading this post, there is only one consecutive segment of minimum values. – epicrose Apr 16 '15 at 11:08