Dynamic programming problem — Finding a suitable algorithm

Bob has $2$ cranes and $M$ available containers ($1 \leq C_i \leq M$) and he has to do $N$ transports from one container to another given an input list (the order of the transports must be respected).

To execute a transport from container $C_i$ to $C_j,$ Bob must choose a crane and move it to $C_i$, pick up the supplies, and then move it to $C_j$, where the crane remains until executing another transport.

The distance between two containers $C_i$ and $C_j$, is always $|i - j|$. We consider that each crane starts at the position of the first container it interacts with.

Since the cranes run on fuel, Bob would like to know, given the transport list, which crane to use for which transport, in order to conserve as much fuel as possible, by minimizing the total distance traveled by the two cranes. Print the minimum distance.

The input file, two_cranes.in, contains, on its first line, two numbers, $N$ and $M$, representing the number of transports Bob has to make, and the total number of available containers. On the next $N$ lines, it will contain one pair $[C_i, C_j]$ per line, representing the start and end positions for each container for the respective transport.

Example test:

$\text{3 10}$

$\text{2 4}$

$\text{5 4}$

$\text{9 8}$

Answer : $5$.

Explanation:

Arbitrarily start with crane 1 at position $2$ and travel to $4$. ($D_0 = | 2- 4| = 2$).

Proceed using crane 1 for the second transport as well. Note that the current position of crane 1 is $4$ (after completing the first transport). So now it travels to positon $5$ then to position $4$, for a total distance of $D_1 = |4 - 5| + |5-4| = 2.$

Finally, use crane 2 for the last transport, so the last distance is $D_2 = |9 - 8| =1$.

Hence, the final answer is $5 = D_0 +D_1 + D_2$.

My attemptS:

First of, I've mistaken this problem to be much easier than it is, hitting it with a straight greedy approach that seemed to fail a lot of test cases. I'd simply go along and choose the closest crane to the $C_i$ of the current transport and increment the distance with the appropriate cost.

Since this didn't work, I figured out that this should actually be solved using dynamic programming, but that's a particularly weak spot of mine. Initially, I found a very simple recurrence relation, but that only seemed to work on two test cases, so I guess it was dumb luck.

I would store a $dp[]$ int array, initialize it with $\infty$, then overwrite $dp[0]$ with the $C_i$ of the first transport. After that, I'd start from $i = 2$, process each transport and let $dp[i] = \min(dp[i - 1], dp[i - 2]) + cost(transport) + 1$ and finally output $dp[N]$.

Alas, this failed as well.

My last approach was trying to find some recurrence relation that I would later optimize using dynamic programming, but I couldn't actually put the pieces together for quite some time.

Data limits

$1 \leq N, M \leq 10^3$

$1 \leq C_i, C_j \leq M \text{ for every such pair}$

$C_i \neq C_j$ for every transport!

Time limits: C++ - $0.3s$, Java - $0.6s$

This problem is just practice, but the course I have it from doesn't give a solution. I've spent too much time on this already, I just want to know the solution, no hints please.

• Would this be more appropriate for SO? – user43389 Dec 5 '16 at 14:27
• Is this a competitive programming problem, is it a homework? Also, what are the constraints on N and M, or more importantly, what is an acceptable complexity of the solution? Is $O(M^2 N)$ good enough? – aelguindy Dec 5 '16 at 14:39
• Hey, @aelguindy, I'll update my post with the information you asked for in a minute. Sorry for overlooking this part. – user43389 Dec 5 '16 at 14:42
• Please update your post to attribute the source of the problem and of all quoted material. See cs.stackexchange.com/help/referencing for our rules and expectations. – D.W. Dec 5 '16 at 17:58
• Have you tried reading the background material and following the advice in our tag wiki on dynamic programming? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. – D.W. Dec 5 '16 at 18:00