@noble_mushtak great solution .As i have already mentioned that there are many approaches . But actually the idea behind explaining just the segment tree solution was to make people learn two problems or you can say it allows us to learn a new standard problem , which can further be used to solve many 
2 Likes
@arunnsit Can you comment on my solution here: Sumbission 10777456 CHSGMNTS. What I have done is since we had to choose 4 indices a, b, c, d such that 1 <= a <= b < c <= d <= N. So I fixed the values a and d increased the size of subarray from d towards a and find the number of subarrays from a that do not intersect. Though in the code as one can see the complexity seems to be O(N^3 * log N), yet it does never even reach O(N^3), and is approxiamately O(N^2 logN), and faster at times depending on the input.
1 Like
Hello,
Although I am familiar with the Segment Trees and had solve basic RMQ questions 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.
Thanks in Advance.
My java code runs under 0.46 seconds. The complexity is slightly higher than N2 but less than NNlogN.
I used duplicate index arrays.
For explanation see this code
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…
https://www.codechef.com/viewsolution/10783875
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…
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…
2 Likes
Well written editorial bruh.
2 Likes
Awesome Soln!
2 Likes
I think you meant dp[i][j] = dp[i][j+1]+1. Right now, you define dp[i][j] in terms of dp[i][j], which doesn’t make sense. Also, in your code, you say that mat[i][j] != 1.
1 Like
Also, you have ans1/2 in your code, so I think you really mean the number of sub-matrices without 0s is double the answer.
1 Like
OK, I finally see how each sub-matrix corresponds to two disjoint intervals in the sub-array. (Also, I have a proof of correctness for this, so I am 100% confident in your solution.) I have to admit, this is a pretty cool solution! I will definitely use the Stock Span-esque technique to count number of sub-matrices in other competitions. Thanks for sharing!
1 Like
NO ,it not . its true that we iterate over all occurrences but see i have already mentioned that we should not try to update any number which is already been updated , right? as it wont change anything . so we actually perform update operation only for every number once . so it wont be nlogn but logn per query.
Got it…!! I made a bad judgement, got the same idea but hesitated to implement due to complexity. Thanks.
Wow…The set makes this a lot easier. My solution has logic very similar to this but does it in C, using binary search and DSU. The reason I don’t use C++ is because I really don’t like how it implements OOP, but I guess the STL is pretty OK.
1 Like
The intuition behind @lohit_97’s solution is that if you have a sub-matrix of 0s with x-coordinates [a, b] and y-coordinates [c, d], then you know that all of the elements in [a, b] are not equal to any element in [c, d], so each sub-matrix corresponds to two disjoint intervals. The best way to understand this is to do a small test case of the solution on paper and try to look at the sub-matrices vs. answers of intervals. Now, the ans += dp[j][i]*(j-st.top()) records the number of rectangles that has width <= dp[j][i] and ends at (j, i).
1 Like
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 -= temp*st.top() cancels out the j term from the beginning and then get rid of the top, so that ans += temp*st.top() cancels out the -st.top() term from the beginning.
1 Like
Your solution seems to be vulnerable to many duplicates, so I tried T=5 and N=1000 with all A_i=1000 and it took about five seconds to run on my computer. However, CodeChef likely did not test this case of all-same elements and your solution really tends to O(N^2\log N) for duplicate-light and duplicate-medium test cases, so I see why this went under time. Even for duplicate-heavy test cases, this is a pretty simple solution, so O(N^3)=O(10^9) running under time is not unreasonable given that the constant is likely small.
1 Like
well actually the query type used in here is far different from RMQ , you should try to solve the spoj problem which i have mentioned first . there are many editorials available for that .
Sorry, by RMQ I didn’t mean only minimum query, I actually meant the problems which have some type of queries as the test cases after formation of Segment tree, and yes I have solved that question.
The problem is just I am not able to connect this problem with the segment tree approach, that why making of segment tree will be helpful to solve the problem, maybe my question is too basic to ask but I am really having problem in understanding.
Hope I am clear with my problem.
okay , lets just go line by line on the editorial and tell me which line you dont understand . i will explain