Problem Link:
Author: tseccodecell
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Traversing array, Binary Search
PROBLEM:
Given N values, we have to apply rearrangements by taking 3 from a value, and give 2 to any other value such that in the end the minimum value of the array is maximum possible
QUICK EXPLANATION:
Make a function which tells if a given speed is possible or not for Barry by taking speeds from those people who have more than required, and giving to those who have less than required. Apply Binary Search on this function to find answer in less time.
EXPLANATION:
Many solutions are possible for smaller subtask but only one will pass the time limit for all cases.
Our main aim is to apply rearrangement so that the minimum value in the array is maximum possible.
For this we have to give values from a higher element value to lower element value. but how much?
Also, if a value is given to an element, it should not be rearranged as that will not result in a better solution than what we already have.
The expected solution is as follows:
Suppose we have to find whether speed X is possible after applying rearrangements.
For this we iterate the array of person speed limits from beginning to end.
if any value is more than X then we can take y = \lfloor\frac{value - x}{3}\rfloor units and give 2*y to other speed limit.
if any value is less than X, and z = \lceil\frac{x - value}{2}\rceil, then we need 2*z units of speed for that value.
After traversing the array and calculating values y and z for each array value, in the end if we get y >= z (speed which we can give >= speed required), then speed of X is possible for the array.
Consider a function f(x) which returns true or false depending on whether X speed value is possible for Barry after optimal rearrangements are applied.
From the above discussion we can see that f(x) will run in O(n) time.
y = 0, z = 0
for i = 0 to N :
if(value[i] > x) y += floor( (value[i] - x) / 3 )
else z += ceil( (x - value[i]) / 2 )
If a speed of X is possible, then all speeds < X are also possible and if speed of X is not possible, then no speed greater than X is possible.
Using this fact, we can iterate the speed from 1 to ‘threshold for barry’ and find the maximum speed possible for Barry. Since for subtask 1, S_i <= 10, this will pass the time limit for subtask 1. (10*O(n))
Using the above observations, we can see that Binary Search can be applied on f(x) to find maximum value in less time.
Using left = 0 and right = threshold + 1, we can apply Binary Search on f(x) to find maximum possible X.
left = 0, right = threshold + 1
// iterative binary search
while(right > left+1) :
mid = (left + right) / 2
if(f(mid) is true) left = mid
else right = mid
In the end, the value in left variable will be the answer
Time Complexity : O(n*log(threshold))
