OLDFAR - Editorial

dynamic-programming
easy-medium
editorial
encoder18

#1

PROBLEM LINK:

Practice
Contest

Author: Yash Gulani

Tester: Ishank Bhardwaj

Editorialist: Ishank Bhardwaj

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a matrix mat with N rows and M columns, find the maximum sum that can be extracted from it, if we traverse a path, starting from mat*[N], with 1<=i< N, and taking exactly two left turns, and ending at mat[j][N], with i< j <= N.

EXPLANATION:

The problem can be divided into two parts:

  1. Profit earned in going from given cell to the rightmost cell in shape of ‘L’.

  2. Profit earned in coming from rightmost cell to a given cell.

For a matrix “mat” with dimensions NxM,

  1. dp*[j] represents the maximum sum that can be obtained by traversing a ‘L’ shaped path formed from the coordinates, (i,j), (x,j) and (x,M) where (i=< x< =N) , for the submatrix with top-left corner at i,j and bottom right corner at N,M.

  2. revCum*[j] represents the sum, mat*[j]+mat*[j+1]+mat*[j+2]…mat*[M]

dp*[j] can be calculated as,
dp*[j] = mat*[j] + max(dp[i+1][j],revCum*[j+1])
(Base cases can be handled accordingly)

After the dp and revCum have been calculated, the matrix can then be traversed and answer can be calculated using
ans=max(ans, revCum*[j]+dp[i+1][j])

AUTHOR’S SOLUTION:

Author’s solution can be found here.