Help in minimum operation?

i have seen some of the submission and even though there is editorial for this question but i am not getting in anyway , can anybody help please?

1 Like

The first observation is that the answer cannot be greater than the n.

suppose we can perform i operations on the k-arrays then we have to find minimum and maximum value possible for each k-arrays.

we can find it greedily by first sort all the k-arrays then -
->the minimum value is calculated by change all the i maximum element to L and sum up the array
->the maximum value is calculated by change all the i minimum element to R and sum up the array

example suppose L = 4, R = 7 array = [4, 5, 6, 7, 7];
For 3 operations
we get minimum sum by replace last 3 elements by L (6 ,7 ,7 by 4 ,4 ,4) and in this way we get minimum sum which equal to 21
we get maximum sum by replace first 3 elements by R (4 ,5 ,6 by 7 ,7 ,7) and in this way we get maximum sum which equal to 35

we do this operation for all k-arrays and store the min and max value for given operation and if all ranges have common point then the answer is
possible else not.

so the remaining task is to perform binary search on number of operations, if for the given MID the answer is possible then go for lower_bound else go for upper_bound.

Time Complexity = (NKlog(N) + Klog(N))

my submission link CodeChef: Practical coding for everyone

2 Likes