DIFFICULTY:
EASY
PREREQUISITES:
BASIC MATRIX OPERATIONS
PROBLEM:
As part of the Kisaan Yojana, the government of India is conducting a survey wherein they will send experts to analyse the plots of farmers across the country and rate them according to various factors like fertility, soil quality, productivity etc. You have to help the farmers decide the contiguous plot of land which will help them earn maximum profit.
Every farmer has a rectangular plot of land and there are n x n blocks in the form of grid. The survey team rates every block in this grid with some positive/ negative cost. Help the farmer select the continuous rectangular section yielding maximum profit.
QUICK EXPLANATION:
The above problem is just a different form of the maximum sum sub-rectangle.
EXPLANATION:
Since sub-matrix with positive sum exists then there exists at least one positive element in the matrix. Hence in order to get AC you just need to find r and c such that M[r][c] > 0 and print
1 1
r c
Since we have some tests with very low number of positive elements we suggest to start any arbitrary smart solution with initializing the answer by this simplest correct sub-matrix.
The good idea how some smart solution can be started is the following. Assume that the set of rows of the sub-matrix is fixed. Than the optimal set of columns will be exactly those columns for which the sum of elements in this column in the selected rows is positive. The same can be applied when the set of columns is fixed.
Now several strategies can be used using this idea:
Choose a random subset of rows (or columns) and find the optimal subset of columns (or rows). Do this multiple times and choose the best.
2. Choose a random subset of rows and find the optimal subset of columns for it. Then find the optimal rows for these columns. Then find the optimal columns for these rows and so on till we stop making the progress.
AUTHOR’S SOLUTION
You can find the solution here