Here is the Problem Statement:
Given array A of N Integers a1 ,a2, a3...... aN . You are also given two integers S and M. You can pick subarray of size S where you have to perform M operation by incrementing the value of each element value by 1. Find the maximum value of minimum value in array A.
Example
Input:
N = 6 ,M = 5 ,S =2
1 2 3 4 5 6
Output:
4
Explaination:
1st opertaion subarray index range (0,1) 2 3 3 4 5 6
2nd opertaion subarray index range (0,1) 3 4 3 4 5 6
3rd opertaion subarray index range (0,1) 4 5 3 4 5 6
4th opertaion subarray index range (2,3) 4 5 4 5 5 6
5th opertaion subarray index range (0,1) 5 6 4 5 5 6
PS: what level problem do you think this will be classified as for a Div.2 round?
Just do binary search on the answer. Now say that you want the minimum to be k. Iterate over the array, if a [i] is less than k, add k — a [i] to the next s elements (i.e. i to i + s — 1), this operation costs k — a [i]. If number of such operations is than M then increase k else decrease k.
Judging the problem in which category varies person to person. I think it is around a Div 2 C problem.
I am really bad when it comes to binary search problems. Can you please explain how you came across this idea? (I mean why did you think that its better to use binary search instead of thinking of some greedy approach)
Actually this is most common type of question where we can use binary search.There is lots of problems on CF and codechef similar to this.If you see them it looks exactly similar and every time we need to only change logic for answering query for BS.for ex.here we can use difference array and iterate over array to count no of operations required to make min element as lets say mid.
Typically, questions of the form "find the maximum value of the minimum value" or "find the minimum value of the maximum value" can be solved using binary search. For such problems, we can essentially binary search on the maximum / minimum values respectively.
Using min heap might work out, with complexity O(M*S*log(N))
Greedy will work here. Insert all N elements in heap, for each of the M operations pop S elements from it, store it and increment every element by 1. Then again push these S elements into heap. Repeat this M times, then element at top of heap at the end of M operations will be the answer.
question says subarray
It will not work for higher constraints.
My solution would be approximately same as preyansh's solution,in the first steps.
Do binary search on the answer, which lies in the interval [1,m+(min element in array)].Lets suppose the answer is ans, we have to check whether this ans is possible in <= m steps.If it is possible ,we should increase answer else should decrease answer.
Now the question is, is it "possible"?We should be able to check it in O(n) time per ans,and not more than that, which gives total time complexity O(n*log(m+(min element in initial array))).
POSSIBLE FUNCTION: Iterate through the array,if we notice a element which is less than ans,number of steps for that element would be ans-a[i],and increase the next s elements (if(i+s-1<n)) by same amount(ans-a[i]).Increasing s consecutive elements can be done in O(1),by a sum array(sum[n]).Add ans-a[i] for sum[i] and subtract it from sum[i+s].Prefix sum of this "sum" array gives you the current value of a[i],at any arbitrary step.(similar problem can be found here).This implementation is to reduce the complexity of POSSIBLE function,from O(s*n) to O(n),which is also important here.
P.S.: It would be a div2 D question according to me.
Could you please tell how to approach if subsequence is given instead of the subarray? Thanks in advance :)
could you help me out related to this as well??