Maximize the value of matrix after doing a specific matrix operation

Problem description

I have tried to solve the problem. But , was unsuccessful.

My approach so far :

  1. Store all the combinations in a temporary 2D array.
  2. Visit one by one cell of the matrix and update the current cell and adjacent cell.
  3. Then storing the value of matrix given by the equation in an auxiliary array , which takes O(n^2)
  4. Now , comparing the results.

This is giving me , TLE. I am not able to come up with overlapping subproblems here.

Can you please help me ?


ANSWERS:


You don't have to deal with combinations at all. It can be shown that the the following conditions on matrix should met: 1. The sum of modified matrixes elements should be equal to the sum of elements of the original matrix. 2. Each element should be in range [1,M]

So the algorithm may be described as:

  1. Calculate the sum of original matrix elements, S.
  2. Fill matrix with ones
  3. Calculate the difference D = S - N*N.
  4. Moving from bottom right corner, fill elements with value V = min(D, M),
  5. decrease D by V, repeat 4 until D>0


 MORE:


 ? Unable to understand algorithm
 ? Executing a dynamic PL/SQL block to execute a sum and return a value
 ? Kickstart 2017(apac) patterns overlap
 ? javascript making change algorithm
 ? What do we call a dynamic programic construct that allows us to compute sums of any range in logarithmic time?
 ? counting by inclusion exclusion
 ? Range Min Query
 ? Max path sum in a 2D array
 ? Dungeon Game Solution explanation
 ? analysis of dynamic programming Matrix-Chain-Order