Find the maximum of ax+b
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}
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]
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 maximumb, 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))