shubhamcr7's blog

By shubhamcr7, history, 14 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • -10
  • Vote: I do not like it  

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one finding the problem statement a bit ambiguous ?

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it could be solved using Segment Tree and Lazy Propagation

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That will be O(NlogN).

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      that's the best thing i can think about, is there any O(N) Solution??? guess not :\

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Are you sure you need O(N)? All I can make up is O(NlogN).

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I think we can use the fact that a[i] will only decrease or at least, never increase.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

»
14 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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)

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        eg: sorted queries : { [3,6,v] , [2,8,v+1] , [4,10,v+3] , [1,5,v+2] }
        prev[i from 3 to 6]=2
        next[i from 3 to 6]=7

        prev[i from 2 to 2]=1
        next[i from 2 to 2]=next[3]=7
        prev[i from next[2] to 8]=1
        next[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.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      I don't think so.
      eg: array : [1 2 3]
      query : [1,3,100000]
      or
      array : [ 10 11 12 ] query : [ 1,3,10 ] => array : [10 10 10] query : [ 1,3,12 ] => array : [10 10 10]

  • »
    »
    14 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    I got it. Good solution!

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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]=7
      prev[3]=prev[7]=2
      So, 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.

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    14 months ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    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
»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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.