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
Haha, thats really nice of you, but won’t it take too much of time.
Anyways lets do it.
The fist thing that i didnt understand in the editorial is that- in the solution of sample problem you mentioned, you are taking 3 values in a node i.e prefix, suffix and sol(which you have described that it contains the solution of interval [X, Y]) whose merging is done by sol=Left.sol + Right.sol + Left.suffix*Right.prefix. If we take 2 leaf nodes having both 0’s then left suffix = 1, right prefix = 1 also both left and right sol are 1 too, therefore the sol of parent node comes to be 3 but not’1’ why?
okay so let the left range be [0,0] which contains ‘0’ and another be [1,1] which also contains ‘0’ . then the parent range will be [0,1] which will contain “00” . right? okay , so the solution is number of substrings which doesn’t contain 1 right ? which is certainly 3 . [0,0],[1,1],[0,1] . any doubts?
ohh yes my bad I mistook the statement…thanks for explaining btw
@noble_mushtak It isn’t. If all the values in the solution are same, my solution will be exactly O(N^2 * logN). See this: CHSGMNTS TRIVIAL INPUT RUN - 0.35 secs
You are welcome. Sorry for so many errors. Thanks for suggesting corrections. I know my solution is correct, what I meant was, I am not sure, about it being O(N^2).
Just to add more,
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.
It is definitely O(N^2) because for some given i, the while loop only runs at most N times because only N items are inserted into the stack (once for each j) which means the while loop can only take off N items from the stack and thus it only runs N times. Thus, since there are N possible i, the while loop gives us O(N^2) instead of O(N^3).