PROBLEM LINK:
Author: Devendra Aggarwal
Tester: Kevin Atienza
Editorialist: Kevin Atienza
DIFFICULTY:
Easy
PREREQUISITES:
maximum subarray sum, dynamic programming, Kadane’s algorithm
PROBLEM:
Ramesh, Suresh, Mahesh, and Mukesh are looking for apartments to live. This city is a matrix of apartments and the only way to travel is to go through apartments (in one of the four cardinal directions), and the group must pay full rent for all rooms they go through.
They want to meet at a room, but Ramesh only goes West, Suresh only goes North, Mahesh only goes East, and Mukesh only goes South. Find the minimum cost for which all of them can live in the city and meet each other. Note that costs can be negative.
QUICK EXPLANATION:
For each location (i,j) and each cardinal direction d, compute f(i,j,d), the minimum total cost of any subarray starting from l and heading to direction d. All such values can be computed with dynamic programming / Kadane’s algorithm in four directions.
The answer is then the minimum among f(i,j,N) + f(i,j,E) + f(i,j,S) + f(i,j,W) - 3C(i,j), where C(i,j) is the cost of apartment (i,j), and N,E,S,W are the directions.
EXPLANATION:
Let’s assume that the room they meet in is (i,j). Since Ramesh only goes west, Ramesh’s room must be on the same row and to the right of (i,j) (or the same as (i,j)). Similarly, Suresh’s room must be on the same column and below (i,j) (or the same), Mahesh’s room must be to the left and Mukesh’s room above. Thus, the final cost will be the total cost of all apartments forming a cross centered at (i,j), as in the following: (assuming X denotes (i,j) and N, E, S, W are the rooms)
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . S . . . . .
. . . . . # . . . . .
. . . . . # . . . . .
. . E # # X # # # W .
. . . . . # . . . . .
. . . . . # . . . . .
. . . . . # . . . . .
. . . . . N . . . . .
. . . . . . . . . . .
Note that the “arms” can be of any length, including zero, in which case the room at the end of the simply “arm” will simply be the cell X.
Now, suppose we know (i,j). and we want to know where to optimally choose the rooms N, E, S, W so the total cost is minimized. In this case, we can compute the optimal length of each “arm” separately. For each of the four directions d, let f(i,j,d) be the minimum total cost of any contiguous sequence of rooms starting at (i,j) and heading at direction d. Then the optimal cost of any cross centered at (i,j) must be
where C(i,j) is the cost of apartment (i,j). The “-3C(i,j)” term cancels out the costs of room (i,j) which was counted four times, one for each arm.
But how do we calculate f(i,j,d)? Since the problem is symmetric in all directions, let’s only focus on one direction, say f(i,j,N). There are two possibilities: whether the length of the arm is one or more than one.
- If the length is one, then the cost is simply C(i,j).
- Otherwise, the optimal sequence starts at room (i,j), and the remaining rooms form a sequence starting at room (i-1,j). The optimal cost for the rooms starting at (i-1,j) must be f(i-1,j,N) by definition, so the optimal sequence starting at (i,j) must be C(i,j) + f(i-1,j,N).
Thus, the optimal sequence starting from (i,j) must be the smaller between the two, or f(i,j,N) = \min(C(i,j), C(i,j) + f(i-1,j,N)) = C(i,j) + \min(0, f(i-1,j,N)). Obviously, if (i,j) is at the topmost row (i.e. i = 1), we can only have f(i,j,N) = C(i,j).
But this means we can compute f(i,j,N) for all (i,j) using dynamic programming, as long as we fill the 2D table in the correct order (because computing f(i,j,N) requires the value of f(i-1,j,N)). One way to do so is to simply fill the table from the top row to the bottom.
For the other directions, the case is very similar, only that the directions to fill the table are different.
Time Complexity:
O(N^2)
