OMAX - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This problem can be solved by combining brute-force and dynamic programming (DP):

  • At first, we find all non-empty sub-matrices, for each we call its two opposite vertices (x1, y1) and (x2, y2) respectively. Then your task is finding the maximal sum of the respective O-region. To do it, we must find the non-empty sub-matrix in range (x1 + 1, y1 + 1)…(x2 - 1, y2 - 1) which has the minimal value to remove. This minimal sum can be found by DP this way:

  • We define F(i, j, k, t) as the minimal sum of a sub-matrix appearing in range (i, j)…(k, t), it should be calculated by Min{F(i + 1, j, k, t), F(i, j + 1, k, t), F(i, j, k - 1, t), F(i, j, k, t - 1), S} where S is sum of the sub-matrix having two opposite vertices respectively (i, j) and (k, t).

  • This solution has the complexity of O((m x n)^2).

TESTER’S SOLUTION

Can be found here.

1 Like

hai i am completely new here and i can’t get what you are talking about here…can you explain me it with the matrix example…i am fresher in compatative programming thanks in advacne

1 Like