You are not logged in. Please login at www.codechef.com to post your questions!

×

CHSGMNTS - Unofficial editorial

18
1

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.

asked 14 Jul '16, 16:24

arunnsit's gravatar image

6★arunnsit
1.0k1611
accept rate: 27%

edited 14 Jul '16, 17:01


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

link

answered 16 Jul '16, 00:16

arunnsit's gravatar image

6★arunnsit
1.0k1611
accept rate: 27%

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

link

answered 18 Jul '16, 14:19

kishore1's gravatar image

2★kishore1
393
accept rate: 0%

Well written editorial bruh.

link

answered 15 Sep '16, 21:28

achlomanziony's gravatar image

4★achlomanziony
511
accept rate: 0%

Awesome Soln!

link

answered 15 Sep '16, 21:43

kainthabhishek's gravatar image

5★kainthabhishek
61
accept rate: 0%

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.

link

answered 14 Jul '16, 21:23

lohit_97's gravatar image

4★lohit_97
3428
accept rate: 4%

edited 19 Jul '16, 00:54

2

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.

(15 Jul '16, 01:49) noble_mushtak5★
2

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.

(15 Jul '16, 04:09) noble_mushtak5★
2

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!

(15 Jul '16, 04:22) noble_mushtak5★

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) lohit_974★

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)$.

(22 Jul '16, 18:20) noble_mushtak5★
Answer is hidden as author is suspended. Click here to view.

answered 15 Jul '16, 14:16

vinay_goel21's gravatar image

3★vinay_goel21
(suspended)
accept rate: 0%

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) arunnsit6★

Got it..!! I made a bad judgement, got the same idea but hesitated to implement due to complexity. Thanks.

(15 Jul '16, 16:28) vinay_goel213★

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.

link

answered 15 Jul '16, 22:15

noble_mushtak's gravatar image

5★noble_mushtak
12813
accept rate: 16%

edited 16 Jul '16, 06:19

@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.

link

answered 16 Jul '16, 05:39

sahilarora.535's gravatar image

4★sahilarora.535
1235
accept rate: 0%

2

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.

(16 Jul '16, 07:10) noble_mushtak5★

@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

(19 Jul '16, 00:23) sahilarora.5354★

It's My aproach

link

answered 14 Jul '16, 23:58

faceless_man's gravatar image

1★faceless_man
1
accept rate: 0%

@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

link

answered 15 Jul '16, 08:48

vishveshcoder's gravatar image

4★vishveshcoder
18729
accept rate: 0%

2

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).

(16 Jul '16, 06:37) noble_mushtak5★
2

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.

(16 Jul '16, 06:42) noble_mushtak5★

Wow,@noble_mushtak has explained my solution far better than I could have explained. :)

(19 Jul '16, 00:55) lohit_974★

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.

(19 Jul '16, 01:06) lohit_974★

Solved using set in C++(O(N^2Log(N))).
Here's the link

link

answered 15 Jul '16, 14:31

omjego's gravatar image

3★omjego
1215
accept rate: 28%

2

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.

(16 Jul '16, 00:02) noble_mushtak5★

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

link

answered 16 Jul '16, 10:09

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

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

link

answered 16 Jul '16, 14:30

shivang_bansal's gravatar image

4★shivang_bansal
1
accept rate: 0%

edited 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) arunnsit6★

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) shivang_bansal4★

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) arunnsit6★

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) shivang_bansal4★

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) arunnsit6★

ohh yes my bad I mistook the statement..thanks for explaining btw

(18 Jul '16, 00:05) shivang_bansal4★
showing 5 of 6 show all

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

link

answered 16 Jul '16, 20:15

ashok1113's gravatar image

4★ashok1113
913
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×40

question asked: 14 Jul '16, 16:24

question was seen: 3,632 times

last updated: 15 Sep '16, 21:43