CHSGMNTS - Unofficial editorial

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 :

  1. x : change the A[X]=1
  2. L R : count the number of substrings in L,R such that no substrings contain a ‘1’.

So the solution is to build a segment tree over the array , with each node [X,Y] containing two values :

  1. prefix: which is basically the continuous number of zeroes starting from X towards Y.
  2. suffix: which is the continuous number of zeroes starting from Y to X.
  3. sol: keeps the value of solution for the node [X,Y]

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

  1. update all the positions which have A[x]=A[b] in our segtree to 1, which we can simply precompute .(one point to note is that suppose if some A[x] has already been marked then theres no need to mark it again)
  2. now add query(b+1,n) to our final solution.

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.

9 Likes

My solution is also O(N^2), I am not 100% confident though.

Considering A as the given array,

I make a 2-D 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.

1 Like

It’s My aproach

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

@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

@arunnsit Isn’t your aproach O(N^3logN). O(N^2) for iteration over array and O(Nlogn) to update all occurances of a[j].norm?

1 Like

Solved using set in C++(O(N^2Log(N))).

Here’s the link

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.

I used binary search and a DSU to create another O(N^2 \log N) solution.

First, get all of the array elements array[].

Loop from i=0 to i=N-1 and make a struct with .content = array[i] and .index = i. Then, insert this struct into sortedArray[] using binarySearch() to figure out how to put it so that sortedArray[] will be sorted by .content and by .index if two elements have the same .content.

Now, loop from j = i+1 to j = N-1. Using sortedArray[] and binarySearch(), find isRepeat[i][j], which is true if and only if array[j] == array[k] for some k in [0, i].

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 answer which we will print. Create a new loop from i=0 to i=N-2. Then, in an inner loop, go from j=0 to j=i. Now, we have a local tempAnswer which will be reset only when we’ve finished the inner loop of j.

Now, in the case that j=0, we need to initialize the DSU, which we’ll call safeIndicies. We start with tempAnswer = 0. We’re also going to build an array called safes[] which breaks the interval [i+1, length-1] into blocks of “safety zones” in which there are no repeat elements with the interval [0, i]. There are safesLength safety zones. The ith element of safes[] tells us the length of the ith safety zones. Note that safety zones can have length 0. Now, we have an inner loop from k=i+1 to k=length-1. If isRepeat[i][k], then we know that the array[k] is a repeat with [0, i], so the current safety zone ends here. This means we add an element to safes[] and add the index of this new safety zone in safes[] into the DSU safeIndicies. We also store the index of this new safe in mappingToSafeIndex[k] so we can find it through k later on. Otherwise, in the case that isRepeat[i][k] is false, we know there is no repeat here, so we simply increment the length of the current safety zone. Lastly, whenever we create a new safety zone with length numSafes, there are numSafes*(numSafes+1)/2 subarrays of that safety zone, all of which are disjoint with [0, i]. Therefore, we increase tempAnswer by numSafes*(numSafes+1)/2 when we create a new safety zone.

Notice how this inner loop of k only runs for j=0. If it ran for all j=0 to j=i, then this would be a O(N^3) solution, but we do something different for j=1 to j=i, so this loop of k only runs from i=0 to i=N-2 and j=0, meaning it is O(N^2).

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 [0, i] and thus some array[k] are no longer repeats with the intervals, so we don’t need to break those safety zones up anymore.

In the case that j is greater than 0, we’re taking array[j-1] out of the interval so we just have the interval [j, i]. Now, we run binarySearch() to find the element in sortedArray[] that comes after .content = array[j-1] and .index = j-1. If this element has a different .content than array[j-1], then we know that there are no elements in the array that is equal to array[j-1], so array[j-1] is not causing any repeats. Therefore, tempAnswer does not change and we move on. If this element has the same .content, but .index less than i, then we know that there is an element equal to array[j-1] inside the interval [j, i], so any repeats caused by array[j-1] will still persist by that other element in [j, i]. Otherwise, we are in the case that when we take out array[j-1], tempAnswer changes because there are repeats with array[j-1] which won’t apply to

In order to account for the changes of taking out array[j-1], we need to join the two safety zones blocked by all of the elements that are equal to array[j-1]. In order to do this, we loop through all of the elements in sortedArray[] starting from the one after .content=array[j-1] and .index=j-1 and then stopping when .content is no longer array[j-1]. We will refer the index of this element in sortedArray[] as k. Since sortedArray[] is sorted by .index and because of the checking we did above, we can be sure that all of these elements have .index greater than i and thus are blocking a safety zone. We find this safety zone with mappingToSafeIndex[sortedArray[k].index]. Now, we need to join the safety zones mappingToSafeIndex[sortedArray[k].index], which we will say has length oldSafe, and mappingToSafeIndex[sortedArray[k].index]+1, which we will say has length newSafe. However, these safety zones may have been joined with other safety zones before, so we use the find() function of the DSU safeIndicies in order to find the parent safety zones of both of the concerning safety zones. Then, for both safety zones, we do tempAnswer -= numSafes*(numSafes+1)/2 because we are getting rid of the safety zones. After that, we join them with dsuUnion() and then we say that this new safety zone has length oldSafe+newSafe+1 (the +1 is there to account for sortedArray[k] itself, as this blocker was previously not counted in either safety zone). Then, we update the corresponding element in safes[] with this new length and do tempAnswer += (oldSafe+newSafe+1)*(oldSafe+newSafe+2)/2 to account for all of the possible intervals of the new safety zone.

Notice how this different inner loop of k only runs at most N-1 times throughout the whole j=1 to j=i loop. This is because in one j=1 to j=i loop, we can only join the two same safety zones once and there are at most N safety zones, so this loop can only run N-1 times since that’s the number of pairs of consecutive safety zones. Thus, because this loop only runs O(N) times for j=1 to j=i, for all i=0 to i=N-2, it is only O(N^2) instead of O(N^3).

In both cases here, tempAnswer represents the number of intervals. Finally, when we’re all done, we print answer.

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.

1 Like

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

@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 :slight_smile:

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

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

I have same complexity O(N^2 logN) using Set. My solution

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. :slight_smile: