Can anyone explain how to solve this Chef Segment Problem. O(N^3) solution is pretty straight forward, i guess. A linear scan of the rest of the array after choosing the start point and end point for the 1st subarray. Constraints hints to O(N^2) solution or maybe O(N^2 LogN). I thought of keeping a dictionary of values -> list of indexes, couldn’t work out more on it. Anyone who can guide ?
Strange thing was, my O(n^3) solution passed for 100.
1 Like
can’t be O(N^3) if it passed…
care to explain the approach ?
It is sad to see O(N^3) solutions pass. Here is my O(N^2 logN) solution:
Let dp[ i ][ j ] denote the number of valid pair of non intersecting segments that start at 'i' and end at 'j'. Then answer to the problem is sum of dp[ i ][ j ] for all possible 'i' and 'j'.
Now only thing that remains is how to find dp[ i ][ j ]. To know dp[ i ][ j ], we will make the best possible use of dp[ i ][ j-1 ]. Let us create a segment tree where value at x^{th} leaf will denote the number of pairs of segments when the left segment has length 'x' starting from 'i'.
Now if we have the segment tree ready for some range [i, j], dp[ i ][ j ] for that segment will be the sum of all leaf nodes(a range sum query).
Now suppose we have the segment tree ready and built for the range [i, j-1]. Now to build it for the range [i, j], we find the first occurrence of ar[ j ] from the i^{th} index. Let this occurrence be at index 'k'. Now observe that for all lengths from 1 to k-i, we have to add 1 to all the nodes of the segment tree because we have found 1 more valid pair of non intersecting segments with such length(from 1 to k-i) of left segment(whose right segment has one more element ar[ j ] added(appended) to it).
Also, we have to update the value of all lengths greater that k-i to zero(or update all leafs at distance greater than k-i from first leaf to 0), because there cannot be any pair of segments in which the left segment has length greater than k-i because ar[ k ] == ar[ j ].
So now we only have to do range update and queries. I hope I was clear.
1 Like
My solution was pretty straightforward. Empirical testing after optimizations showed that it ran in O(N^2) time.
The solution is pretty straightforward, pretty much how you defined it in the post actually. Iterate through all combinations of start and end points and then linear scan the rest of the array. I used several optimizations to make this fast. First of all, i pre processed the array to find all the duplicates and associated with each element, the indexes of all of it’s duplicates. Now on each iteration i can simply create a boolean array of all the numbers in the range of index_end+1 to index n-1 in the array and then count all the subarrays between the various duplicates.
Naturally that’d be O(N^3). But you can optimize this by two observations:
-
Say that your start is j and your last end was k. Then [j,k+1] would have the same answer as [j,k] if the k+1th element also occurs in the range [j,k] (Easily checked thanks to preprocessing). This makes it easy to traverse a duplicate heavy array to the point that it becomes almost constant time (empirically).
-
For a duplicate light array, recognize that if you just counted all the elements in the jth iteration, and the j+1th point is unique (i.e has no duplicates in the array. Can be checked in constant time thanks to the preprocessing) then the answer for the j+1th element is the same as the answer for the jth element, minus the count for [j,j].
Together, both of those optimizations provide you what essentially becomes an O(N^2) solution. I tried this approach with both duplicate heavy arrays, duplicate light arrays and arrays with varying percentage levels of duplicates, all of whom run the code empirically in quadratic time. It’s hard to prove mathematically that the solution would always run in quadratic time, but empirical testing shows that it does indeed run in quadratic time.
The above two solutions are quite good. 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 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
My solution : https://www.codechef.com/viewsolution/10808005
Getting TLE in last two test cases. Any help would be appreciated.
can you explain your 2nd point more precisely ?
Even O(N^3) solution passes all the test cases in case, you pre-calculate values of (N*(N+1)/2) in an array ! 
Here is link to my code :
[1]
[1]: https://www.codechef.com/viewsolution/10818592
1 Like
let’s say that you have an array [1,2,3,1]. Let say that you have just calculated all the possible pairs for the second element. I.e you’d found the number of pairs compatible with [2,2],[2,3],[2,4]. Then for [3,3] and [3,4] the answer is the same as that of all the subarrays that begin with the second element, except for [2,2] IF 2 has no duplicates in the entire array. This can be done in constant time.
I have solved it using the following approach.
A segment of length of n contain n*(n+1)/2 subarrays.
We start taking each subarray, insert all indexes of values present in it and calculate answer for each subarray.
Initially we have taken no subarray, so initial length = length of array. So temporary answer=length*(length+1)/2.
We insert index of current element and all it’s other indexes where it is present in array. Each index breaks our original array into two parts(any of them maybe of zero or positive length) which can be calculated easily. Then we can subtract and add accordingly to our temporary answer. After that we add that value to our final answer.
But this approach was working slowly on my PC and it got AC! Here is my submission. You can see the testcase at the bottom of the page. It took 1.36s on my PC but on Ideone it took 0.2s. I accidently made this submission public. I have discussed about that here
1 Like
Nice (hi 5 :P), I too had the same idea, at first it looked like a O(N^3LgN) solution, but I realised that it was actually O(N^2LgN)…I noticed that we’d have to add at most O(N) “break” points for each index…each of these points breaks the segment formed by the two nearest “break” points (one to the left and one to the right) into two parts…
My solution, https://www.codechef.com/viewsolution/10713524, O(n^3), ran in 0.65s, which was fast enough for this problem.
Hello,
Although I am familiar with the Segment Trees 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. 