Mine took just 0.08 sec for the longest task… coded in C… underlying algorithm i devised although is of complexity O(n^3)… I managed to device one algorithm which in most of the cases could use the pre-calcualted values from the table… so. the inner most for loop comes not often… However its not fully dynamic programming… but most of the part resembles dynamic programming… To put it into clearly… its some kind of mixture of dynamic programming with less contribution of backtracking…
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.
plz… upvote my post… sothat i could earn enough karma to post an explanation of my algorithm for Chef and segments problem which could be done in O(n^2) time complexity by using dynamic programming approach…
and i coded this in C language… and the longest task took just 0.08 seconds…
Ofcourse, i used mixture of dynamic programming with a little bit of backtracking in my code… but now i observed that if we are clever enough we could even eliminate the backtracking…
1 Like
@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?
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
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.