Блог пользователя shubhamcr7

Автор shubhamcr7, история, 8 лет назад, По-английски

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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    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.

    • »
      »
      »
      8 лет назад, # ^ |
      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.

»
8 лет назад, # |
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)

  • »
    »
    8 лет назад, # ^ |
    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?

    • »
      »
      »
      8 лет назад, # ^ |
      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)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +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]=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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 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

  • »
    »
    8 лет назад, # ^ |
    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I got it. Good solution!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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]=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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 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.

  • »
    »
    8 лет назад, # ^ |
    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