Encontre o máximo de ax + b

14

Você recebe uma lista de ( a, b ) e uma lista de x . Calcule o eixo máximo + b para cada x . Você pode assumir a , b e x são inteiros não negativos.

Seu programa ou função deve ser executado no tempo esperado (aleatoriamente se o seu código envolver isso, não na entrada) O ( n log n ) tempo em que n é o comprimento total da entrada (soma ou máximo dos comprimentos de ambas as listas).

Isso é código-golfe. O menor código vence.

Exemplo

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

Resultado:

[11 12 14 16 20]

Explicação:

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

Nota sobre a complexidade:

Se você usou um built-in com uma boa complexidade de caso médio e pode ser randomizado para obter facilmente a complexidade esperada em teoria, você pode assumir que seu idioma fez isso.

Isso significa que, se seu programa puder ser testado como O ( n log n ), possivelmente com exceções de maiúsculas e minúsculas por causa da implementação do seu idioma, mas não puder ser visto logicamente em seu próprio código, diremos que é O ( n log n ).

jimmy23013
fonte
Parece-me que os resultados esperados deveriam ser [11 12 12 15 4]. ???
Bob Jarvis - Restabelece Monica
@BobJarvis É o máximo de ax + b para o x correspondente, mas para todos (a, b) na lista. Alterado para tornar o exemplo menos enganador.
jimmy23013
comprimento total da entrada = comprimento dos pares (a, b) mais o comprimento da matriz de x?
Optimizer
@Optimizer Right.
precisa saber é o seguinte
Por que está claro que isso é possível O(n log(n))? Você pode fornecer um algoritmo de referência?
flawr

Respostas:

1

Pitão - 99 98 bytes

Esta é praticamente uma tradução direta da resposta em Python do @ KeithRandall. Definitivamente pode ser jogado muito mais. Em breve postarei uma explicação .

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

Leva duas listas delimitadas por vírgula, separadas por vírgulas por meio de stdin.

Experimente aqui

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
Maltysen
fonte
10

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

Calcula o casco convexo iterando pela entrada a,bem aordem crescente . O casco convexo é registrado Husando o formato em -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bnque xié a coordenada x da interseção de a{i-1},b{i-1}e ai,bi.

Então, eu itero as entradas xna ordem classificada, truncando o casco convexo para acompanhar o andamento.

Tudo é linear, exceto os tipos que são O (n lgn).

Execute-o como:

>>> 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}
Keith Randall
fonte
@ user23013: corrigido
Keith Randall
@KeithRandall Na última etapa, você busca em Hlinearmente para cada xno X, não é ?. Não é possível termos complexidade O (n ^ 2) quando ambas as listas têm o mesmo comprimento?
Coredump
1
@ Coredump: Eu procuro Hlinearmente para cada um x, mas, como faço para xs, lembro onde a última pesquisa parou e inicie a próxima pesquisa lá. Portanto, o whileloop interno pode executar no máximo O (n) vezes em todos x(mesmo que possa executar O (n) vezes para qualquer indivíduo x).
Keith Randall
@ Coredump: Observe que o mesmo acontece com o whileloop interno no primeiro forloop.
Keith Randall
@KeithRandall Eu perdi isso, obrigado. Esperto!
Coredump
6

Haskell, 204 271 bytes

Edit : jogou golfe ainda mais, atualizando o casco convexo como uma lista (mas com a mesma complexidade da versão não destruída), usando "split (x + 1)" em vez de "splitLookup x" e removendo todas as chamadas de função qualificadas, como Predule. foldl.

Isso cria uma função f que espera a lista de (a, b) pares e uma lista de valores x. Eu acho que vai ser deslumbrado longitudinalmente por qualquer coisa na família APL usando as mesmas idéias, mas aqui vai:

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

Uso da amostra:

[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]

Funciona em tempo O (n log n); veja abaixo para análise.

Edit: Aqui está uma versão não-gasta com a análise big-O e uma descrição de como tudo funciona:

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]
Matt Noonan
fonte
2

Lisp comum - 648 692

Com uma pesquisa binária real.

(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)

Explicação

Seja n o comprimento de (a, b) ek o comprimento dos pontos.

  • classifique (a, b) por a, então b - O (n.ln (n))
  • remova entradas para duplicatas a(linhas paralelas), mantendo apenas a linha paralela com o máximo b, sempre maior que a outra (evitamos divisões por zero ao calcular interseções) - O (n)
  • comprima o resultado - O (n) : quando tivermos elementos consecutivos (a0, b0) (a1, b1) (a2, b2) na lista classificada, de modo que o ponto de interseção de (a0, b0) e (a1, b1 ) é maior que o de (a1, b1) e (a2, b2), então (a1, b1) pode ser ignorado com segurança.
  • construa uma lista de (xab) elementos, em que x é o valor até qual linha ax + b é o máximo para x (essa lista é classificada por x graças às etapas anteriores) - O (n)
  • dada essa lista, crie um lambda que execute uma verificação de intervalo para sua entrada e calcule o valor máximo - a árvore binária é construída em O (n) (consulte /programming//a/4309901/124319 ). A pesquisa binária que será aplicada possui complexidade O (ln (n)) . Com o exemplo de entrada, criamos a seguinte função (essa função é então compilada):

    (LAMBDA (X)
      (IF (< X 4)
          (IF (< X 2)
              (IF (< X -6)
                  (+ (* 0 X) 4)
                  (+ (* 1 X) 10))
              (+ (* 2 X) 8))
          (+ (* 4 X) 0)))
    
  • aplique essa função a todos os elementos - O (k.ln (n))

Complexidade resultante: O ((n + k) (ln n))) no pior cenário.

Não podemos fornecer uma estimativa de complexidade para o número total de entradas (n + k), porque k e n são independentes. Por exemplo, se n for wrt k assintoticamente desprezível , a complexidade total seria O (k) .

Mas se supormos que k = O (n) , a complexidade resultante é O (n.ln (n)) .

Outros exemplos

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

E se movermos as aspas para ver o que está sendo calculado, podemos ver que nem precisamos fazer nenhuma comparação (depois que a primeira lista for pré-processada):

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

Aqui está outro exemplo (retirado de um comentário):

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

A função efetiva:

(MAPCAR
  (LAMBDA (X)
    (IF (< X 4)
        (+ (* 1 X) 20)
        (+ (* 4 X) 8)))
  '(1 2 3 4 5))
coredump
fonte
O (n log n + k) está obviamente em O ((n + k) log (n + k)).
precisa saber é o seguinte
Qual intérprete você está usando? Ideone cede (LIST* A B C R) should be a lambda expression.
precisa saber é o seguinte
@ user23013 Desculpe, eu esqueci de (use-package :optima) (edição ...)
coredump
@ user23013 Receio não poder fazer o Ideone carregar uma biblioteca externa. Para testar, faça o download do SBCL (ou talvez outro, embora eu só tenha testado no SBCL) e instale o quicklisp . Em seguida, você pode (ql: quickload: optima) fazer o download e instalar optima. Finalmente, o código que forneci deve ser avaliável.
Coredump
Ele retornou (MAPCAR (EVAL (LAMBDA (X) ...e avalia a resposta. Você deixou algum código de depuração lá?
precisa saber é o seguinte