Optimising the maximum value in a list in O(nlog(range of bounds)) time

Question

Currently I got a problem in which we have two arrays say x=[x1,x2,x3,...,xn] and array y=[y1,y2,y3,...,yn] and a value say k. Now I have to generate an array say z=[z1,z2,z3,...,zn] from k, such that z1+z2+z3...+zn=k . For different z generated what will be the minimum value of max of [(x1-z1)*y1, (x2-z2)*y2, (x3-z3)*y3, ...., (xn-zn)*yn]. i.e minimum value of maximum of (x[i]-z[i])*y[i] . For e.g. if x=[2,3,4,1,6] and y=[3,5,2,7,3] and k=4 than taking z=[0,1,0,0,3] gives array [6,10,8,7,9] for which maximum is 10 which is also minimum maximum.
I designed an algorithm which computes it in O(nlog(n)+k) .Here if k will be very large than my algorithm will be inefficient. Can we do it in O(n) or O(nlog(n)) . My Current Algorithm is:

1. l=[] //initialize empty array
2. for i from 0 to n:
     l.append(x[i]*y[i],y[i])
3. Sort l in decreasing order of (x[i]*y[i])
4. while(m>0):
     num=l[0][0]-l[1][0] //take difference of two largest x[i]*y[i]
     t=(num/l[0][1])+1 //Choose appropriate number to subtract to minimize 
                         the maximum
     t=max(0,t)        // t must not be negative
     l[0][0]=l[0][0]-t*l[0][1]
     Put l[0] at correct position in sorted list l //Since value of 
                                                     l[0][0] has 
                                                     changed we will 
                                                     place it at 
                                                     correct position 
                                                     in already sorted  
                                                     l (using binary 
                                                     search)
     m=m-t
5.Print l[0][0] as the minimum maximum

Answer 1

If you can calculate or estimate the lower and upper bound on your answer (which is minimum possible maximum value of your resulting array) then you can use binary search to solve this problem.

To binary search the answer we now need a predicate, let's call it p.

p(val) = true if there exists an array z such that the max value of (xi-zi) * yi is less than equal to val and false otherwise

To prove that binary search will work using this predicate we need to prove two things:

1. if p(a) = true then p(b) = true for all b >= a
2. if p(a) = false then p(b) = false for all b <= a

These two statements can be proved using the definition of the predicate.

To evaluate the predicate for a given value, try to estimate each zi:

1. if xi * yi > val then choose a minimum possible zi such that xi*yi - zi*yi <= val
2. otherwise choose maximum possible(in magnitude) zi such that xi*yi - zi*yi <= val is still true

Now, there will be three cases:

1. if sum of zi is <k, then you can can select any one positive zi and increase it to a point that sum of zi becomes k. You can see that increasing this zi won't effect the predicate value as maximum of (xi-zi)*yi would still be less than k. In this case predicate will be true.
2. if sum is exactly k, then again true.
3. if the sum is greater than k then the result is false. As in this case, no negative zi can be chosen and decreased more because its already at the maximum value allowed.

Now, its time for some code.

low = -100
high = 100 # these two are assumed values

x = [2, 3, 7, 1, 6]
y = [3, 5, 2, 7, 3]
k = 4

def p(val):
    sum_zi = 0  # sum of possible zi
    for idx in range(len(x)):
        if x[idx]*y[idx] > val:
            diff = x[idx]*y[idx] - val
            zi = (diff + y[idx] - 1) // y[idx]
            sum_zi += zi
        else:
            diff = x[idx]*y[idx] - val
            zi = diff // y[idx]
            sum_zi += zi
    return sum_zi <= k

while low < high:
    mid = (low + high)//2
    if p(mid):
        high = mid
    else:
        low = mid+1

print("Min possible max value", low)
# output = 10

Using this you can calculate your result in nlog(range of bounds)