ReZa.BN's blog

Minimum possible value
By ReZa.BN, history, 5 years ago, In English

We have an array with length N. In an operation we increase M adjacent elements of array by 1. After K operations what is the minimum possible value for the maximum element of array. 1 ≤ N, M ≤ 10^5 1 ≤ K ≤ 10^8

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose instead we fix an value $$$V$$$ and want to answer the question:

Is there a way to apply $$$K$$$ operations such that the maximum element doesn't exceed $$$V$$$.

It is not too hard to see that there is a greedy solution to this. We apply the $$$K$$$ operations one by one picking the leftmost interval such that none of its values is equal to $$$V$$$. The naive implementation is quite slow (at least $$$O(NM)$$$ if not worse). You can implement it fairly easily in $$$O(NlogN)$$$ using appropriate data structures.

Interestingly enough I think you can implement the greedy in $$$O(N)$$$ with a clever dequeue approach.

Finally, as you have probably guessed, we can look for the smallest $$$V$$$ such that the greedy succeeds by binary search for the answer. The complexity of the approach can be anywhere from $$$O(NMlogK)$$$ (or worse) to $$$O(NlogK)$$$ depending on your implementation of the greedy. The easiest approach that would pass is likely $$$O(NlogN)$$$ for the greedy and $$$O(NlogNlogK)$$$ for the whole thing, though if the TL is strict or the grading system slow, faster may be necessary.

I've not described the greedy implementations in details intentionally. Feel free to ask for more help on that part, but only after you've spent considerable amount of time trying to figure it out yourself.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your answer. I have some questions. First if we apply K operations one by one, won' t it cause the solution to be O(KMN)? And after some thinking, I couldn't find a way to implement the greedy O(NlogN) solution. I'll appreciate if you give me some hint about it.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Applying the one-by-one is how you visualise the greedy approach. In reality you would, of course, not apply them one by one. If you can apply the operation on the range $$$[L,R]$$$ at least once, then you would apply it as many times as possible at once (which can be calculated from the maximum element in $$$[L,R]$$$).

      Now if you imagine sliding an interval of length $$$M$$$ starting from $$$[1,M]$$$ and sliding rightwards, we can construct a naive solution. Simply find the maximum value in the interval, apply a bulk of operations, and then slide the interval rightwards.

      Finding the maximum number in the interval and updating the numbers after the operations are each $$$O(M)$$$. You can slide the interval at most $$$O(N)$$$ times, so this solution is $$$O(NM)$$$.

      Faster solutions will rely on tricks to speed up the $$$O(M)$$$ part. The most brute faster solution would be to just use a segment tree to do both operations (get max and increase value in interval). With a lazy logging approach this would result in $$$O(logN)$$$ per query and hence $$$O(NlogN)$$$ for a single run of the greedy. This is a very crude approach and you can come up with neater solutions with the same complexity.

      → Reply