A segment of length of n contain n*(n+1)/2 subarrays.
We start taking each subarray, insert all indexes of values present in it and calculate answer for each subarray.
Initially we have taken no subarray, so initial length = length of array. So temporary answer=length*(length+1)/2.
We insert index of current element and all it’s other indexes where it is present in array. Each index breaks our original array into two parts(any of them maybe of zero or positive length) which can be calculated easily. Then we can subtract and add accordingly to our temporary answer. After that we add that value to our final answer.
But this approach was working slowly on my PC and it got AC! Here is my submission. You can see the testcase at the bottom of the page. It took 1.36s on my PC but on Ideone it took 0.2s. I accidently made this submission public. I have discussed about that here
Although I am familiar with the Segment Trees but I am not able to understand the solution of this problem, I mean what is the insight to solve this problem using segment trees.
It would be really helpful if anyone could explain it in a bit detail.
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…
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…
let’s say that you have an array [1,2,3,1]. Let say that you have just calculated all the possible pairs for the second element. I.e you’d found the number of pairs compatible with [2,2],[2,3],[2,4]. Then for [3,3] and [3,4] the answer is the same as that of all the subarrays that begin with the second element, except for [2,2] IF 2 has no duplicates in the entire array. This can be done in constant time.
Nice (hi 5 :P), I too had the same idea, at first it looked like a O(N^3LgN) solution, but I realised that it was actually O(N^2LgN)…I noticed that we’d have to add at most O(N) “break” points for each index…each of these points breaks the segment formed by the two nearest “break” points (one to the left and one to the right) into two parts…
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.
