### shubhamcr7's blog

By shubhamcr7, history, 23 months ago, ,

Given an array of n elements. ‘n’ operations needs to be performed on the array. For each operation start_index, end_index,trim_value is given. One has trim the value starting from the start_index to end_index inclusive. If the value at that index is more than or equal to trim value then make it equal to trim_value else leave it as it is. After performing ‘n’ operations find the maximum value of the array.

•
• -10
•

 » 23 months ago, # |   0 Am I the only one finding the problem statement a bit ambiguous ?
•  » » 23 months ago, # ^ |   +31 Not really. It's as messy as your hair.
•  » » » 23 months ago, # ^ |   +3 Not really messy, but I don't think there is a solution that works in O(N).
 » 23 months ago, # |   0 I think it could be solved using Segment Tree and Lazy Propagation
•  » » 23 months ago, # ^ |   +1 That will be O(NlogN).
•  » » » 23 months ago, # ^ |   +3 that's the best thing i can think about, is there any O(N) Solution??? guess not :\
 » 23 months ago, # |   +1 Are you sure you need O(N)? All I can make up is O(NlogN).
 » 23 months ago, # |   +3 I think we can use the fact that a[i] will only decrease or at least, never increase.
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 I had the same thoughts. Default answer is the maximum of all trims, the answer better that this can only be found in a point which is not covered by any segments. If there is a fast way to check whether the point is covered or not then we are done.Update: But the fastest way to check whether it's covered is O(N). I give up.
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 I am thinking in direction of a partial sum solution (where you update l_index and r+1_index)I mean, if we just want to know if a point is never updated, we can simply do that, right?Actually, we have to keep track of only those trim values that are <= max(a[i]) before each query. So, I guess maybe we can do something in offline mode.
•  » » » » 23 months ago, # ^ |   0 We can do it simply, but it won't be O(N).
•  » » » » » 23 months ago, # ^ |   0 Yeah, I realized that.
 » 23 months ago, # | ← Rev. 2 →   +4 First sort all the updates in the increasing order of trim value using radix sort or counting sort.Now, maintain 2 arrays: next[i] and prev[i] denoting the immediate next and previous untrimmed element from i.Iterate over the updates in the increasing order of trim value and trim all elements in the required range , updating next[] and prev[] as you go.If we consider the initial sorting of updates to be O(N) , total time complexity is O(N)Edit: sorry, seems like it might not be possible to keep track of prev and next in amortized O(N)
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 Good thinking!But, if I understand correctly, it's not O(n). It's like dsu so the complexity is not exactly O(n) but close to it. Isn't it?
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 Everything apart from sort will be amortized O(N), because each element will be trimmed at max. once. It's not like dsu, you simply have to update prev[] and next[] as follows:when you trim ith element, set: prev[next[i]] = prev[i]; next[prev[i]] = next[i]; Edit: this cannot be updated for previously deleted elements, hence seems like solution is not O(N)
•  » » » » 23 months ago, # ^ |   +3 eg: sorted queries : { [3,6,v] , [2,8,v+1] , [4,10,v+3] , [1,5,v+2] }prev[i from 3 to 6]=2next[i from 3 to 6]=7 prev[i from 2 to 2]=1next[i from 2 to 2]=next[3]=7prev[i from next[2] to 8]=1next[i from next[2] to 8]=9 next[i from ( next[ next[4]==7 ]==9 ) to 10]=11 -> we see a chain forming But you're claiming that this chain will always have a size<=2, right? Let me think about it for a moment.
•  » » » » » 23 months ago, # ^ |   0 You are right, I was only maintaining prev and next links for non-trimmed elements, but for this we would need the first non-trimmed element in the range of each query, which will bring in an extra log(n) factor. Looks like we are back to square one :D
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 This can be done even easier. If the sorting is O(N) then we can just sort the operations by left border and mark all the positions that were changed in O(N). Then we assume the default maximum value to be the maximum of all trims and watch every single position in O(N). If the position is not marked then we compare it with the maximum and check if it's better. Upd: mistake here, sorry.But is the sorting really O(N)? OP hasn't clarified it.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +3 I don't think so.eg: array : [1 2 3]query : [1,3,100000]orarray : [ 10 11 12 ] query : [ 1,3,10 ] => array : [10 10 10] query : [ 1,3,12 ] => array : [10 10 10]
•  » » » » 23 months ago, # ^ |   0 Yeah, you are right. I made a mistake.
•  » » 23 months ago, # ^ | ← Rev. 4 →   0 I got it. Good solution!
•  » » » 23 months ago, # ^ |   +5 By keeping a pointer of next and previous, you are skipping over the previously trimmed region. As the queries are sorted in increasing order, thus, once updated, an index won't get trimmed again.eg: sorted queries : { [3,6,v] , [2,8,v+1] , [1,5,v+2] , [4,6,v+3] }Once the segment [3,6] has been trimmed to v, it can't be trimmed further. So we skip it for all other queries.next[3]=next[6]=7prev[3]=prev[7]=2So, when we get the second query, we only update linearly from l to min(prev[i],r) and from max(l,next[i]) to r.
•  » » » » 23 months ago, # ^ |   0 Can someone prove the complexity? It doesn't look O(n) to me. The implementation follows a dsu like storage of representative node. The complexity is close to O(n) but not O(n). At least, that's what I think.
•  » » 23 months ago, # ^ | ← Rev. 7 →   0 Improving on @gvaibhav21's approach ,Time Complexity — O(n) sort trim_value using radix sort(tvs) tvs //({ [3,6,v] , [2,8,v+1] , [4,10,v+3] , [1,5,v+2] }), trim_value_store updated[] = {1} for tv in tvs i = tv.left while(i <= tv.right) arr[i] = min(arr[i], tv.val) i += updated[i] updated[i] = tv.right-i+1
 » 12 months ago, # |   -11 one way u could do it is, first sort the queries using counting sort. then maintain 1 thing for each element of the array the end of the range associated with some trim value already applied to that element. now when you try to process the queries, you start with the smallest trim value and do the trimming for its range. now when some other query having overlapping range is encountered, we can process the range normally but the part already processed by some other smaller trim values range can be skipped with the help of the value that we are storing, which helps us to jump directly to next element of interest. thus no element of the array is visited twice.