PREREQUISITES: Segment trees. Well there are actually multiple solutions for this question of varying complexities . I will explain the solution with O(N^2(Logn)) complexity that involves segment trees and its one of the fairly standard problems of segment tree. So for now lets just consider another problem i.e given an array A with all element zero , you can perform two types of query on the array :
So the solution is to build a segment tree over the array , with each node [X,Y] containing two values :
so now the merge function of two nodes Left and Right will be: { sol=Left.sol + Right.sol + Left.suffix*Right.prefix prefix=(Left.size()==Left.prefix)?(Left.size()+right.prefix:Left.prefix) suffix=(Right.size()==Right.suffix)?(Right.size()+Left.suffix:Right.suffix)} this is actually a standard problem with many variants , you can solve one of them over here . now we can simply perform both the queries in O(logn) per query time.(we just need to compute sol of nodes L,R). Lets solve the original problem now . Lets fix an 'a' first and then iterate over b (from a to n) , this will certainly produce all substrings , while incrementing b
for every 'a' clear the segtree again .At last , print the final solution . complexity is pretty clear , iterating over a and b will take O(n^2) time with querying and updation for every b will be logn . it makes it (N^2logN) , which is good enough to pass . c++ solution. asked 14 Jul '16, 16:24

@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 :) answered 16 Jul '16, 00:16

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 precalcualted 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.. answered 18 Jul '16, 14:19

My solution is also O(N^2), I am not 100% confident though. Considering A as the given array, I make a 2D boolean matrix where, mat[i][j] = 1 if A[i]=A[j] else it is 0. Then I make a DP matrix, where for each ith row, dp[i][j] = dp[i][j+1]+1 if mat[i][j]!=1, else dp[i][j]=0. Now, here's a bit of magic for you. Our answer is half of the possible submatrices of DP matrix which contain only 0 as an element. I use Stock Span kind off implementation to count the number of submatrices with only 0s. You can have a look at my code here. Well if you want some help, as to how, I thought of this, you can comment here. answered 14 Jul '16, 21:23
2
I think you meant
(15 Jul '16, 01:49)
2
Also, you have
(15 Jul '16, 04:09)
2
OK, I finally see how each submatrix corresponds to two disjoint intervals in the subarray. (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 Spanesque technique to count number of submatrices in other competitions. Thanks for sharing!
(15 Jul '16, 04:22)
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).
(19 Jul '16, 00:51)
It is definitely $O(N^2)$ because for some given
(22 Jul '16, 18:20)

Answer is hidden as author is suspended. Click here to view.
answered 15 Jul '16, 14:16
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.
(15 Jul '16, 14:54)
Got it..!! I made a bad judgement, got the same idea but hesitated to implement due to complexity. Thanks.
(15 Jul '16, 16:28)

I used binary search and a DSU to create another $O(N^2 \log N)$ solution. First, get all of the array elements Loop from Now, loop from This is the first part and is done in $O(N^2\log N)$ because the loop and inner loop has $O(N^2)$ and the binary search is $O(\log N)$. For the second part, we have a global Now, in the case that Notice how this inner loop of At this point, you're likely wondering what the DSU is for. The DSU will allow us to join two safety zones together once we've taken an element out of In the case that In order to account for the changes of taking out Notice how this different inner loop of In both cases here, The second part here also takes $O(N^2\log N)$ because the loop and inner loop has $O(N^2)$ and the binary search takes $O(\log N)$. Any DSU operations can effectively be ignored because with the DSU I used, they take $O(\alpha(N))$ which is very, very slow. Thus, overall, this algorithm is $O(N^2\log N)$ time using only binary search and a DSU, without a segment tree. answered 15 Jul '16, 22:15

@arunnsit Can you comment on my solution here: Sumbission 10777456 CHSGMNTS. What I have done is since we had to choose 4 indices answered 16 Jul '16, 05:39
2
Your solution seems to be vulnerable to many duplicates, so I tried
(16 Jul '16, 07:10)
@noble_mushtak It isn't. If all the values in the solution are same, my solution will be exactly
(19 Jul '16, 00:23)

@lohit_97 Can you please explain in your code, why are you multiplying by temp each time? And what was the intuition behind this solution? Thanks answered 15 Jul '16, 08:48
2
The intuition behind @lohit_97's solution is that if you have a submatrix of 0s with xcoordinates [a, b] and ycoordinates [c, d], then you know that all of the elements in [a, b] are not equal to any element in [c, d], so each submatrix 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 submatrices vs. answers of intervals. Now, the
(16 Jul '16, 06:37)
2
Then, eventually, a
(16 Jul '16, 06:42)
Wow,@noble_mushtak has explained my solution far better than I could have explained. :)
(19 Jul '16, 00:55)
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 2D 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.
(19 Jul '16, 01:06)

Solved using set in C++(O(N^2Log(N))). answered 15 Jul '16, 14:31
2
Wow...The
(16 Jul '16, 00:02)

I have same complexity O(N^2 logN) using Set. My solution answered 16 Jul '16, 10:09

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. :) answered 16 Jul '16, 14:30
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 .
(16 Jul '16, 14:45)
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.
(16 Jul '16, 15:14)
okay , lets just go line by line on the editorial and tell me which line you dont understand . i will explain
(16 Jul '16, 17:05)
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?
(16 Jul '16, 18:41)
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?
(16 Jul '16, 18:59)
ohh yes my bad I mistook the statement..thanks for explaining btw
(18 Jul '16, 00:05)
showing 5 of 6
show all
