Please read the new rule regarding the restriction on the use of AI tools. ×

conan45's blog

By conan45, history, 4 weeks ago, In English

Two type of operations

Type1: replace A[i] by A[i]-1

Type2: Replace A[i] to 0.

Determine maximum length of subarray that can be obtained if all elements of subarray are zero and you can apply max operations of x and y of type 1 and 2 respectively.

Constraints: 1<=T<=7

1<=N<=1e5

0<=A[i]<=1e9

0<=Y<=1e9

0<=X<=1e14.

Reference Images:

Tags dp
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

we can binary search on answer length of subarray

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Like yeah i got his idea but i am not getting a 0(n) solution even to check if that length mid satisfies, like in detail say me how to check that??

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      let's say you are checking if you can find a subarray with length of at least $$$mid$$$

      iterate through all subarrays of size $$$mid$$$ and keep a $$$cnt$$$ of how many $$$0$$$ elements in each subarray

      if there's a subarray with $$$mid-cnt <= x+y$$$, then you can turn that whole subarray into $$$zeros$$$

      there's an edge case when $$$x=0$$$, then you can only use the subarrays that starts with a $$$0$$$

      this should be $$$O(n)$$$

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Like i am sorry, the initial post was wrong, like see now i have corrected the question can you explain it to me now

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          now i'm not sure if i understand correctly...

          why does the sample test gives $$$4$$$? the way i understand it should be $$$6$$$

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I have changed the question its A[i]=A[i-1], its changed to A[i]=A[i]-1.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              so for every subarray of size mid, smallest elements should be used first to exhaust all ops of type 1, then after that remaining elements<=y.

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

              Sorry for the late reply :(

              Lets do a different approach. For each index $$$l$$$, let it be a potential start of our subarray and find $$$f(l)$$$ as the furthest end away from l that we can turn the subarray $$$[l,f(l)]$$$ into zeros

              If $$$a[l]==0$$$ and we found a potential end $$$r$$$, we pick $$$x$$$ largest elements in $$$[l,r]$$$ and apply opertaion $$$1$$$ to turn them to zeros, and the other elements we can chip away with operation $$$2$$$. So to be able to turn $$$[l,r]$$$ into zeros, we need to satisfy $$$Sum(l,r)-SumOfBig(l,r)<=y$$$, with $$$SumOfBig$$$ meaning the sum of the X biggest elements in $$$[l,r]$$$

              If $$$a[l]!=0$$$,we use up one of the first type operation to make it $$$0$$$, and find $$$f(l)$$$ similarly like case above

              $$$Sum(l,r)$$$ can be done in $$$O(1)$$$ with prefix sum; and we can find $$$SumOfBig(l,r)$$$ in $$$O(log(n)^2)$$$ with binary search, combined with Persistent Segment Tree or Persistent Fenwick Tree.

              Our complexity for each potential $$$r$$$ is $$$O(log(n)^2)$$$ so we cant afford another binary search. Use 2 pointers instead.

              However there's an easy mistake to fall into. Unlike normal 2 pointers, here $$$f(l)$$$ can be less than $$$f(l+1)$$$ because we must waste a first type operation if the second case occurs for $$$l+1$$$. So we need to do 2 pointers seperately for the 2 cases. I guess my explanation for doing the 2 pointers seperately might be unclear, if you are not sure about it you can ask later :D

              Edit: just finished dinner :) my solution above is $$$O(n*log^2)$$$ but we can inprove it to $$$O(n*log)$$$

              instead of using persistent data structures combined with binary search, as you move the pointers you can insert elements into a BST(for example Treap) or a skiplist

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Is this an ongoing online assessment?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by conan45 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by conan45 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can work this with 2 pointers maintaining the start and end points of a subarray while also keeping Y largest elements that are present in that subarray which are done by type-2 operation and making sure that all the elements that are not a part of Y largest elements are done by type-1 operation.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by conan45 (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

yes