### PROBLEM LINK:

**Author:** Aditya Paliwal

**Tester:** Teja Vardhan Reddy

**Editorialist:** Aswin Ashok

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

DP

### PROBLEM:

You are given a **M x M** grid representing a city. A cell in this grid is represented as

(i,j), i.e. the cell at the i-th row and j-th column in the grid. You own two trucks A

and B that deliver goods. **Truck A is located at at (Ax,Ay) and Truck B is located at
(Bx,By)**. Both trucks have an infinite number of goods. The two trucks could initially

be at the same location. The distance to travel between cells (i1,j1) and (i2,j2) is the

**Manhattan Distance, i.e., |i1−i2|+|j1−j2| units.**

Your company has to serve N orders, where the i-th order is located at position

(xi,yi). An order is said to be served if some truck moves to the location of the i-th

order. Additionally, the i-th order can be served only once all order numbers from

1 to i−1 have been served.

### EXPLANATION:

There are two trucks at **(Ax,Ay) and (Bx,By) and N orders (Xi,Yi)**, each of these

orders must be satisfied by either of these two truck (ie one of these trucks has to

move to Xi,Yi to satisfy order i). The Trucks can only satisfy order i if all the orders

before it are satisfied. The cost of satisfying an order is the Manhattan distance

covered by the truck from its current position to reach the coordinates of that

order. We have to find the minimum combined distance traveled by both trucks.

### SOLUTION:

We can use Dynamic Programming to solve this problem. Let n=N+2, assume that

we have **n** orders and consider the initial positions of the trucks as the first two

orders.

**dp[i][j]** represents the minimum cost such that the first truck delivered its last order

at i{th} coordinate and second truck delivered its last order at j{th} coordinate.

So **dp[0][1]=0** (The coordinates are numbered from **0 to n-1**)

Now we can find the minimum cost by iterating over the orders from 2^{nd} coordinate to n-1^{th} coordinate.

**There are two cases:**

- The truck delivering i^{th} order delivered also delivered i-1^{th} order the other

truck can deliver its last order at coordinates from**0 to i-2**

**dp[i][j]=dp[i-1][j]+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);**

//truck 1 moved from i-1 th to i th coordinate

**dp[j][i]=dp[j][i-1]+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);**

//truck 2 moved from i-1 th to i th coordinate

**(j=0 to i-2)**

- If i-1^{th} order is delivered by the other truck then the truck delivering i^{th} order

can deliver its last order at coordinates from**0 to i-2**

**dp[i][j]=min(dp[i][j],dp[k][j]+abs(x[i]-x[k])+abs(y[i]-y[k]));**

// truck 1 moved from kth coordinate to ith coordinate

**dp[j][i]=min(dp[j][i],dp[j][k]+abs(x[i]-x[k])+abs(y[i]-y[k]));**

// truck 2 moved from kth coordinate to ith coordinate

**(j=i-1, k=0 to i-2)**

**The Final answer is the minimum of dp[n-1][i] and dp[i][n-i] (i=0 to n-2).**

### TIME COMPLEXITY

For each i, j goes from 0 to i-2 and k goes from 0 to i-2. The value

of i goes from 2 to n-1. The time complexity of calculating dp will be 2*((N+1)*N/2).

The final answer can be found out in linear time. Therefore overall time complexity

will be O(N^2).

### SOLUTIONS LINKS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.