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.