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 ;	
}

complete code link

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
Wow great, thanks for the links, +1 for the fusharblog link.

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?

Thank you for the links. This was really helpful.

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

Here is my code … if u need it anytime

1 Like

I am not familiar with much standard problem … but i thought there can be maximum this much number of submatrix if i am able to compute correctly the maximum value obtained from a smaller submatrices then the same can be applied to even bigger size sub matrices .

1 Like

@ma5termind your code gave WA