Temukan maksimum kapak + b

14

Anda diberi daftar ( a, b ), dan daftar x . Hitung kapak maksimum + b untuk setiap x . Anda dapat menganggap a , b dan x adalah bilangan bulat non-negatif.

Program atau fungsi Anda harus berjalan dalam yang diharapkan (ke keacakan jika kode Anda melibatkan itu, bukan input) O ( n log n ) waktu di mana n adalah total panjang input (jumlah atau maksimum panjang dari kedua daftar).

Ini adalah kode-golf. Kode terpendek menang.

Contoh

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

Keluaran:

[11 12 14 16 20]

Penjelasan:

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

Perhatikan tentang kerumitannya:

Jika Anda menggunakan builtin yang memiliki kompleksitas kasus rata-rata yang baik, dan dapat diacak untuk mendapatkan kompleksitas yang diharapkan secara teori, Anda dapat mengasumsikan bahasa Anda melakukan itu.

Itu berarti, jika program Anda dapat diuji dalam O ( n log n ), mungkin dengan pengecualian kasus tepi karena penerapan bahasa Anda, tetapi tidak dapat dilihat secara logis dalam kode Anda sendiri, kami akan mengatakan itu adalah O ( n log n ).

jimmy23013
sumber
Bagi saya sepertinya hasil yang diharapkan adalah [11 12 12 15 4]. ???
Bob Jarvis - Reinstate Monica
@ BobJarvis Ini adalah maksimum dari ax + b untuk x yang sesuai, tetapi untuk semua (a, b) dalam daftar. Diubah agar contohnya kurang menyesatkan.
jimmy23013
total panjang input = panjang (a, b) pasangan plus panjang array x?
Pengoptimal
@Optimizer Benar.
jimmy23013
Mengapa jelas bahwa itu mungkin O(n log(n))? Bisakah Anda memberikan algoritma referensi?
flawr

Jawaban:

1

Pyth - 99 98 byte

Ini adalah terjemahan langsung dari jawaban Python @ KeithRandall. Pasti bisa bermain golf lebih banyak. Saya akan segera memposting penjelasan .

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

Mengambil dua daftar yang dibatasi koma, dipisahkan dengan koma melalui stdin.

Coba di sini

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
sumber
10

Python, 214 byte

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

Hitung cembung lambung dengan iterasi melalui input a,bdalam aurutan yang meningkat . Cembung lambung direkam Hmenggunakan format di -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bnmana xikoordinat x dari persimpangan a{i-1},b{i-1}dan ai,bi.

Kemudian saya mengulangi input xdalam urutan diurutkan, memotong lambung cembung untuk mengikuti saat saya pergi.

Semuanya linier kecuali untuk jenis yang O (n lgn).

Jalankan seperti:

>>> 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
sumber
@ user23013: diperbaiki
Keith Randall
@KeithRandall Pada langkah terakhir, Anda mencari di Hlinear untuk setiap xdi X, apakah Anda tidak ?. Apakah tidak mungkin bahwa kita memiliki kompleksitas O (n ^ 2) ketika kedua daftar memiliki panjang yang sama?
coredump
1
@coredump: Saya mencari Hsecara linear untuk masing-masing x, tetapi karena saya melakukan ini xagar saya ingat di mana pencarian terakhir berhenti dan mulai pencarian berikutnya di sana. Jadi whileloop dalam dapat mengeksekusi paling banyak O (n) kali di semua x(meskipun mungkin mengeksekusi O (n) kali untuk setiap individu x).
Keith Randall
@coredump: Perhatikan bahwa hal yang sama terjadi pada whileloop dalam pada forloop pertama .
Keith Randall
@ KeithRandall saya melewatkan itu, terima kasih. Pintar!
coredump
6

Haskell, 204 271 byte

Sunting : bermain golf lebih jauh dengan memperbarui convex hull sebagai daftar (tetapi dengan kompleksitas yang sama dengan versi yang tidak diklik), menggunakan "split (x + 1)" bukannya "splitLookup x", dan menghapus semua panggilan fungsi yang memenuhi syarat seperti Predule. foldl.

Ini menciptakan fungsi f yang mengharapkan daftar (a, b) pasangan dan daftar nilai x. Saya kira itu akan terpesona oleh apa pun dalam keluarga APL menggunakan ide yang sama, tapi begini saja:

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

Penggunaan sampel:

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

Ini bekerja dalam waktu O (n log n); lihat di bawah untuk analisis.

Sunting: Ini versi yang tidak disatukan dengan analisis big-O dan deskripsi cara kerjanya:

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
sumber
2

Gangguan Umum - 648 692

Dengan pencarian biner yang sebenarnya.

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

Penjelasan

Biarkan n menjadi panjang (a, b) dan k panjang titik.

  • sortir (a, b) dengan a, lalu b - O (n.ln (n))
  • hapus entri untuk duplikat a(garis paralel), hanya mempertahankan garis paralel dengan maksimum b, yang selalu lebih besar dari yang lain (kami mencegah pembagian dengan nol saat menghitung persimpangan) - O (n)
  • kompres hasilnya - O (n) : ketika kita memiliki elemen konsekutif (a0, b0) (a1, b1) (a2, b2) dalam daftar yang diurutkan, sedemikian sehingga titik persimpangan (a0, b0) dan (a1, b1) ) lebih besar dari salah satu (a1, b1) dan (a2, b2), maka (a1, b1) dapat dengan aman diabaikan.
  • membangun daftar elemen (xab), di mana x adalah nilai up-to-which kapak + b adalah maksimal untuk x (daftar ini diurutkan berdasarkan x berkat langkah sebelumnya) - O (n)
  • diberikan daftar itu, buat lambda yang melakukan pemeriksaan interval untuk inputnya dan menghitung nilai maksimum - pohon biner dibangun di O (n) (lihat /programming//a/4309901/124319 ). Pencarian biner yang akan diterapkan memiliki O (ln (n)) kompleksitas . Dengan input contoh, kita membangun fungsi berikut (fungsi itu kemudian dikompilasi):

    (LAMBDA (X)
      (IF (< X 4)
          (IF (< X 2)
              (IF (< X -6)
                  (+ (* 0 X) 4)
                  (+ (* 1 X) 10))
              (+ (* 2 X) 8))
          (+ (* 4 X) 0)))
    
  • terapkan fungsi itu untuk semua elemen - O (k.ln (n))

Kompleksitas yang dihasilkan: O ((n + k) (ln n))) dalam skenario terburuk.

Kami tidak dapat memberikan perkiraan kompleksitas untuk jumlah total input (n + k), karena k dan n independen. Sebagai contoh, jika n secara asimtotik diabaikan, maka k , maka total kompleksitasnya adalah O (k) .

Tetapi jika kita mengira bahwa k = O (n) , maka kompleksitas yang dihasilkan adalah O (n.ln (n)) .

Contoh lainnya

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

Dan jika kita memindahkan kuotasi mundur untuk melihat apa yang sedang dihitung, kita dapat melihat bahwa kita bahkan tidak perlu membuat perbandingan apa pun (begitu daftar pertama diproses sebelumnya):

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

Ini adalah contoh lain (diambil dari komentar):

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

Fungsi yang efektif:

(MAPCAR
  (LAMBDA (X)
    (IF (< X 4)
        (+ (* 1 X) 20)
        (+ (* 4 X) 8)))
  '(1 2 3 4 5))
coredump
sumber
O (n log n + k) tentu saja dalam O ((n + k) log (n + k)).
jimmy23013
Juru bahasa apa yang Anda gunakan? Ideone memberi (LIST* A B C R) should be a lambda expression.
jimmy23013
@ user23013 Maaf, saya lupa (use-package :optima) (mengedit ...)
coredump
@ user23013 Saya khawatir saya tidak bisa membuat Ideone memuat perpustakaan eksternal. Untuk pengujian, silakan unduh SBCL (atau mungkin yang lain, meskipun saya hanya menguji pada SBCL) dan menginstal quicklisp . Kemudian, Anda dapat (ql: quickload: optima) untuk mengunduh dan menginstal optima. Akhirnya, kode yang saya berikan harus dapat dievaluasi.
coredump
Itu dikembalikan (MAPCAR (EVAL (LAMBDA (X) ...yang mengevaluasi jawaban. Apakah Anda meninggalkan beberapa kode debug di sana?
jimmy23013