CHSGMNTS July Challenge

@jvj_iit can you explain your solution in a better way

@lohit_97 , can u explain ur method in detail?

could be done in just O(n^2) time using dynamic programming… ofcourse, i used dynamic programming with a little bit of backtracking viz could be removed if we are clever enough… now i found an algorith of O(n^2) complexity…

Well, we have to select two segments such that no two elements are common in those two segments. So, when I am making a 2-D DP matrix, I taking my 1st segment from ROW and 2nd segment from COLUMN. So, R1 to R2 is my first segment and C1 to C2 is my second segment. Now, if there is any element common in R1 to R2 and C1 to C2 (i.e. two segments) we will, automatically have “1” in that submatrix, hence it is ruled out from my answer. So, basically, I have to select those submatrices which no element has only 0 as its elements.

@lohit_97 , yep i understood what mat and dp are doing but how did u optimise , that part i dont get.Apparently ur answer is half the sum of ans variables.What does this ans and cum variables represent?

The ans += dp[j][i](j-st.top()) records the number of rectangles that has width <= dp[j][i] and ends at (j, i).Then, eventually, a dp[j][i] smaller than the top of the stack might come later, at which point we need to get rid of the top of the stack because the width is too big to apply to this cell and thus undo the ans += dp[j][i](j-st.top()) at the beginning. Therefore, we do temp=dp[st.top()][i] so that temp is the dp[j][i] from the beginning.

Then, ans -= tempst.top() cancels out the j term from the beginning and then get rid of the top, so that ans += tempst.top() cancels out the -st.top() term from the beginning.

Thanks to @noble_mushtak