# How to solve

Can any one give some pointers on how to solve these two problems??

I was able to solve the rest three during contest but was out of luck (or knowledge) for these two.

Hello dragonemperor ,

I just solved this one CodeChef: Practical coding for everyone .

First of all thanks for asking this question . It was a good question and i solved it using Dynammic Programming …

Try some test cases and convince yourself that this problem cannot be solved using some kind of greedy technique .

let us fomulate a DP recurrence .(small constraints gives me an idea of N^2*M^2 DP solution ).

DP[MAXN][MAXN][MAXN][MAXN] → deontes our DP table .

DP[s1][e1][s2][e2] → denotes the maximum energy that can achieved from submatrix [s1,e1] (top left coordinates) to [s2,e2] (bottom right coordinates) .

DP[s1][e1][s2][e2] = sum of submatrix (s1,e1,s2,e2) + max( DP[s1+1][e1][s2][e2],DP[s1][e1+1][s2][e2],DP[s1][e1][s2-1][e2],DP[s1][e1][s2][e2-1] )

have a look at this simple code .

```LL solve(int s1,int e1,int s2,int e2){

if(s2 < s1 || e2 < e1)
return 0 ;
LL &ret = DP[s1][e1][s2][e2] ;
if(ret != -1){
return ret ;
}
ret = 0 ;
LL sum_matrix ;
sum_matrix = ( M[s2][e2] - M[s2][e1-1] - M[s1-1][e2] + M[s1-1][e1-1] ) ;
ret = max(ret,sum_matrix+solve(s1+1,e1,s2,e2)) ;
ret = max(ret,sum_matrix+solve(s1,e1+1,s2,e2)) ;
ret = max(ret,sum_matrix+solve(s1,e1,s2-1,e2)) ;
ret = max(ret,sum_matrix+solve(s1,e1,s2,e2-1)) ;
return ret ;
}
```

2 Likes

Hello

I read this one too CodeChef: Practical coding for everyone

This is very standard problem and can be solved using matrix exponentiation . Such Problem are easily solvable following dynammic programming approach but due to high constraints techniques used to solve such problem is called Solving Linear Recurrences .

Here is link for learning 1

Here is link for learning 1

Here is link for learning 3

This will surely help .

2 Likes

@ma5termind

I don’t get the approach. Can you please elaborate a little bit. Also, how did you come up with something like that? Does it fall under some standard dp category or something?

Welcome coders btw i am unable to submit code for this problem .