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?
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
ohh yes my bad I mistook the statementā¦thanks for explaining btw
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
@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).
Well written editorial bruh.
2 Likes
Awesome Soln!
2 Likes