Find the maximum of ax+b

Question

You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.

Your program or function must run in expected (to the randomness if your code involves that, not the input) O(nlogn) time where n is the total input length (sum or maximum of the lengths of both lists).

This is code-golf. Shortest code wins.

Example

[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]

Output:

[11 12 14 16 20]

Explanation:

11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0

Note about the complexity:

If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.

That means, if your program can be tested to be in O(nlogn), possibly with edge case exceptions because of the implementation of your language, but cannot be seen logically in your own code, we'll say it is O(nlogn).

Answer 1

Pyth - 99 98 bytes

This is pretty much a direct translation of @KeithRandall's Python answer. It can definitely be golfed a lot more. I will be posting an explanation soon.

K[_1Z;FNShQAkdNW&>K2>+*k@K_3d+*@K_2@K_3eK=K<K_3)~K[c-eKd-k@K_2kd;FNSeQW&>K2>N@K2=K>K3)aY+*hKN@K1;Y

Takes two comma delimited lists, separated by commas through stdin.

Try it here

K                  K=
 [  )              A List containing
  _1               Negative 1
  Z                Zero
FN                 For N in
 ShQ               Sorted first input
Akd                Double assign k and d
 N                 To N
 W                 While
  &                Logical And
   >K2             K>2
   >               Greater Than
    +*k@K_3d       K[-3]*k+d
    +              Plus
     *@K_2@K_3     K[-2]*K[-3]
     eK            K[-1]
  =K               K=
   <K_3            K[:-3]
  )                Close while loop
 ~K                K+=
  [      )         List constructor
   c               Float division
    -              Minus
     eK            K[-1]
     d             d
    -              Minus
     k             k
     @K_2          K[-2]
   k               k
   d               d
 ;                 End list and for loop
FN                 For N in
  SeQ              Sorted second input
  W                While loop
   &               Logical and
    >K2            K[2:]
    >              Greater than
     N             N
     @K2           K[2]
   =K              K=
   >K3             K[3:]
  )                Close while loop
  aY               Y.append - Y is empty list
   +               Plus
    *hKN           (K+1)*N
    @K1            K[1]
;                  Close out everything
Y                  Print Y

Answer 2

Python, 214 bytes

S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b>H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x>H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R

Computes the convex hull by iterating through the input a,b in increasing a order. The convex hull is recorded in H using the format -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn where xi is the x coordinate of the intersection of a{i-1},b{i-1} and ai,bi.

Then I iterate though the input xs in sorted order, truncating the convex hull to keep up as I go.

Everything is linear except for the sorts which are O(n lgn).

Run it like:

>>> print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}

Answer 3

Haskell, 204 271 bytes

Edit: golfed much further by updating the convex hull as a list (but with the same complexity as the ungolfed version), using "split (x+1)" instead of "splitLookup x", and removing all qualified function calls like Predule.foldl.

This creates a function f which expects the list of (a,b) pairs and a list of x values. I guess it will be blown away length-wise by anything in the APL family using the same ideas, but here it goes:

import Data.Map
r=fromListWith max
[]%v=[(0,v)]
i@((p,u):j)%v|p>v#u=j%v|0<1=(v#u,v):i
(a,b)#(c,d)=1+div(b-d)(c-a)
o i x=(\(a,b)->a*x+b)$snd$findMax$fst$split(x+1)$r$foldl'(%)[]$r$zip(fmap fst i)i
f=fmap.o

Sample usage:

[1 of 1] Compiling Main             ( linear-min.hs, interpreted )
Ok, modules loaded: Main.
λ> f [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] [1..5]
[11,12,14,16,20]
λ> f [(1,20), (2,12), (3,11), (4,8)] [1..5]
[21,22,23,24,28]

It works in O(n log n) time; see below for analysis.

Edit: Here's an ungolfed version with the big-O analysis and a description of how it all works:

import Prelude hiding (null, empty)
import Data.Map hiding (map, foldl)

-- Just for clarity:
type X = Int
type Y = Int
type Line = (Int,Int)
type Hull = Data.Map.Map X Line
slope (a,b) = a

{-- Take a list of pairs (a,b) representing lines a*x + b and sort by
    ascending slope, dropping any lines which are parallel to but below
    another line.

    This composition is O(n log n); n for traversing the input and
    the output, log n per item for dictionary inserts during construction.
    The input and output are both lists of length <= n.
--}
sort :: [Line] -> [Line]
sort = toList . fromListWith max

{-- For lines ax+b, a'x+b' with a < a', find the first value of x
    at which a'x + b' exceeds ax + b. --}
breakEven :: Line -> Line -> X
breakEven p@(a,b) q@(a',b') = if slope p < slope q
                                 then 1 + ((b - b') `div` (a' - a))
                                 else error "unexpected ordering"

{-- Update the convex hull with a line whose slope is greater
    than any other lines in the hull.  Drop line segments
    from the hull until the new line intersects the final segment.
    split is used to find the portion of the convex hull
    to the right of some x value; it has complexity O(log n).
    insert is also O(log n), so one invocation of this 
    function has an O(log n) cost.

    updateHull is recursive, but see analysis for hull to
    account for all updateHull calls during one execution.
--}
updateHull :: Line -> Hull -> Hull
updateHull line hull
    | null hull = singleton 0 line
    | slope line <= slope lastLine = error "Hull must be updated with lines of increasing slope"
    | hull == hull' = insert x line hull
    | otherwise = updateHull line hull''
    where (lastBkpt, lastLine) = findMax hull
          x = breakEven lastLine line
          hull' = fst $ x `split` hull
          hull'' = fst $ lastBkpt `split` hull

{-- Build the convex hull by adding lines one at a time,
    ordered by increasing slope.

    Each call to updateHull has an immediate cost of O(log n),
    and either adds or removes a segment from the hull. No
    segment is added more than once, so the total cost is
    O(n log n).
--}
hull :: [Line] -> Hull
hull = foldl (flip updateHull) empty . sort

{-- Find the highest line for the given x value by looking up the nearest
    (breakpoint, line) pair with breakpoint <= x.  This uses the neat
    function splitLookup which looks up a key k in a dictionary and returns
    a triple of:
        - The subdictionary with keys < k.
        - Just v if (k -> v) is in the dictionary, or Nothing otherwise
        - The subdictionary with keys > k.

    O(log n) for dictionary lookup.
--}
valueOn :: Hull -> X -> Y
valueOn boundary x = a*x + b
    where (a,b) = case splitLookup x boundary of
                    (_  , Just ab, _) -> ab
                    (lhs,       _, _) -> snd $ findMax lhs


{-- Solve the problem!

    O(n log n) since it maps an O(log n) function over a list of size O(n).
    Computation of the function to map is also O(n log n) due to the use
    of hull.
--}
solve :: [Line] -> [X] -> [Y]
solve lines = map (valueOn $ hull lines)

-- Test case from the original problem
test = [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] :: [Line]
verify = solve test [1..5] == [11,12,14,16,20]

-- Test case from comment
test' = [(1,20),(2,12),(3,11),(4,8)] :: [Line]
verify' = solve test' [1..5] == [21,22,23,24,28]

Answer 4

Common Lisp - 648 692

With an actual binary search.

(use-package :optima)(defun z(l e)(labels((i(n m)(/(-(cadr m)(cadr n))(-(car n)(car m))))(m(l)(match l((list* a b c r)(if(<(i a b)(i b c))(list* a(m(list* b c r)))(m(list* a c r))))(_ l)))(f(x &aux(x(cdr x)))`(+(*,(car x)x),(cadr x)))(g(s e)(let*((q(- e s))(h(+ s(floor q 2)))d)(if(> q 1)(let((v(g s h))(d(pop l)))`(if(< x,(car d)),v,(g(1+ h)e)))(cond((not(car (setq d (pop l))))(f d))((> q 0)`(if(< x,(car d)),(f d),(f(pop l))))(t(f d)))))))(setq l(loop for(a b)on(m(remove-duplicates(#3=stable-sort(#3# l'< :key'cadr)'< :key'car):key 'car)) by #'cdr collect`(,(when b(i a b)),(car a),(cadr a))))`(mapcar(eval(lambda(x),(g 0(1-(length l)))))',e)))

(z '((2 8) (4 0) (2 1) (1 10) (3 3) (0 4)) '(1 2 3 4 5))
=> (11 12 14 16 20)

Explanation

Let n be the length of (a,b) and k the length of points.

• sort (a,b) by a, then b - O(n.ln(n))
• remove entries for duplicate a (parallel lines), retaining only the parallel line with the maximum b, which is always greater than the other (we prevent divisions by zero when computing intersections) - O(n)
• compress the result - O(n) : when we have consecutives elements (a0,b0) (a1,b1) (a2,b2) in the sorted list, such that the intersection point of (a0,b0) and (a1,b1) is greater than the one of (a1,b1) and (a2,b2), then (a1,b1) can safely be ignored.
• build a list of (x a b) elements, where x is the value up-to-which line ax+b is maximal for x (this list is sorted by x thanks to previous steps) - O(n)

• given that list, build a lambda that perform an interval check for its input and computes the maximum value - the binary tree is built in O(n) (see https://stackoverflow.com/a/4309901/124319). The binary search that will be applied has O(ln(n)) complexity. With the example input, we build the following function (that function is then compiled):

  (LAMBDA (X)
    (IF (< X 4)
        (IF (< X 2)
            (IF (< X -6)
                (+ (* 0 X) 4)
                (+ (* 1 X) 10))
            (+ (* 2 X) 8))
        (+ (* 4 X) 0)))
  

• apply that function for all elements - O(k.ln(n))

Resulting complexity: O((n+k)(ln n))) in a worst-case scenario.

We can't provide a complexity estimate for the total number of inputs (n+k), because k and n are independant. For example, if n is asymptotically negligeable w.r.t. k, then the total complexity would be O(k).

But if we suppose that k=O(n), then the resulting complexity is O(n.ln(n)).

Other examples

(z '((1 10) (1 8) (1 7)) '(1 2 3 4 5))
=> (11 12 13 14 15)

And if we move backquotes to see what is being computed, we can see that we don't even need to make any comparison (once the first list is preprocessed):

(MAPCAR (LAMBDA (X) (+ (* 1 X) 10)) '(1 2 3 4 5))

Here is another example (taken from a comment):

(z '((1 20) (2 12) (3 11) (4 8)) '(1 2 3 4 5))
=> (21 22 23 24 28)

The effective function:

(MAPCAR
  (LAMBDA (X)
    (IF (< X 4)
        (+ (* 1 X) 20)
        (+ (* 4 X) 8)))
  '(1 2 3 4 5))