I am not sure if i am missing something in the solution presented here.
Consider this example: say we start at s, the attraction at s+1 is 1, at s+2 is 2, at s+3 is 50 and at s-100 is 100. In other places it is 0. Value of d is 107.
The optimal solution is: take 1, 2 and 100. But if I follow the solution at analysis, it will be 100 if we go left first and 53 if we go right first. The reason is, in the optimal solution we spend 4 days right side (move right + attraction). But if f() is computed independent of the fact that we will move left later then f(4) = s+3 and we gain 50 but the optimal solution will say don't go that far to s+3 rather you collect 1 and 2 in 4 days and move left. So it is not true that f(t) be always the optimal point if we had the reduced problem.
Can any one explain where I am going wrong?
I guess you missed this part: "We first iterate on d0 the days we want to spend on moving and visiting cities to the right of, and including, start. Using the solution to the intermediate case, we know f(d0). Then we know we can spend d−d0−(f(d0)−start)−1 days on the cities to the left of start.", i.e. you will find the optimal solution when you choose some value of d0 that will allow you to travel to and visit cities 1 and 2 only, and then you'd spend the remaining days on the path to the left, picking 100 as well.
Umm I read those. Let me proceed case by case: d0 = 1, f(d0) = s. because in 1 day we can collect max 0 attraction and s is the left most of them. d0 = 2, f(d0) = s + 1, because in 1 day we can collect max 1 attraction from s+1. d0 = 3, f(d0) = s + 1, max = 1, leftmost = s + 1 d0 = 4, f(d0) = s + 3, max = 50, leftmost = s + 3.
The part I am having trouble in the formula: d — d0 — (f(d0) — start) — 1 is, though you are running loop over d0, you are considering: d0 + f(d0) and also max_profit for d0. So, it might be possible that for fixed d0, you go less further right and make less profit but go much further in right, or go much further in right make huge profit and go less left. What I dont see is, how can these two cases be handled by simply looping over number of days spent for "moving right + collecting attraction".
Can you please correct me if I am doing wrong by showing me the values of f() for 1 to say 5?
Oh, I see, it seems to me you're right.. It's weird.
I'm not sure if I understand you correctly, but I'm guessing you're missing this part of the solution:
For each direction, we consider 2 cases. Either we come back to the center after going to the furthest point, or we just remain at the furthest point. The optimal choice may differ between these 2 cases, so we calculate f() separately for each case. Then to merge the 2 sides, add case1 on left to case2 on right, or case2 on left to case1 on right.
Sorry, I dont get you. Can you explain with my example? What would be appropriate d0 for my example?
If you're going to return to start point, then it's not like f(4)=s+3. It's f(6) = s+3, you're counting returning moves as well. It is easier to think of that in that way Suppose we are given sequence a_1, ..., a_(k-1), a_k, a_(k+1), ..., a_n, where a_k is out starting point.
Firstly we consider a case when we firstly go left, return and go right.
We consider sequences:
a_(k+1), a_(k+2), ...
and
0, a_(k-1), 0, a_(k-2), ...
Then we count those f's for them and obtain a result/ f(i) for particular sequence is a best profit we can get using i days for walking and sightseeing (and not returning back). After considering that case we consider opposite case, firstly going right, returning, and going left. I think that you misunderstood definition of f in case we have to return back.
What do you mean by: 0, a_(k-1), 0, a_(k-2), ...?
If, f and g are defined differently, like: g only going towards the direction and f includes returning, then the whole solution makes sense. But I had the impression that f and g are defined exactly the same way (except starting point and direction).
However, another thing regarding time complexity, when we divide at g(M/2) it is not guaranteed to make the list half as well right? If I am not wrong, it is /4 in worst case. Which is fine. (I think something similar will happen for f() too)
I meant that "If f(d) is a function, which tells us, what is the best profit when we have to go towards, sightsee and return to starting point in d days for sequence of cities a_(k+1), a_(k+2), ... , then f(d) is also a function which counts what is the best profit when we have to go towards and sightsee (we do not demand returning back now!) for sequence of cities 0, a_(k+1), 0, a_(k+2), ..." Is it more clear now? Those zeros tells us that we have to have time to return back. If we want to reach some city (and this is first phase with returning) than we have to return back in future, so we can as well treat that we have to use 2 units of time to reach that city which corresponds to inserting those zeros as artificial cities to make cities reaching times two times longer.
I see. Makes sense. Clever way to design going & returning to going. Thanks.