Saat menumpuk buku, Anda biasanya ingin meletakkan yang terbesar di bagian bawah dan yang terkecil di bagian atas. Namun, OCD laten saya membuat saya merasa sangat tidak nyaman jika saya punya dua buku di mana satu lebih pendek (tingginya) tetapi lebih lebar dari yang lain. Tidak peduli urutan mana saya menempatkan mereka, buku teratas akan melampaui buku bawah di satu sisi.
Sebagai contoh, katakanlah satu buku memiliki dimensi (10,15)
dan yang lain memiliki dimensi (11,14)
. Tidak peduli ke arah mana saya menempatkan mereka, saya mendapatkan overhang. Tetapi jika saya memiliki buku dengan dimensi (4,3)
dan (5,6)
, saya bisa menghindari menggantung dengan menempatkan yang terakhir di bawah yang pertama.
Untuk keperluan tantangan ini, kami hanya akan mempertimbangkan perubahan terkait dengan buku di bawah ini . Misalnya jika saya memiliki setumpuk (5,5)
, (3,3)
, (4,4)
(bukan bahwa setiap waras orang akan melakukan itu), penghitungan buku atas sebagai overhang, meskipun tidak melampaui buku bawah. Demikian pula, tumpukan (3,3)
, (3,3)
, (4,4)
juga hanya memiliki satu overhang, meskipun buku atas memperluas luar satu bawah.
Tantangan
Diberi daftar pasangan integer untuk dimensi buku, urutkan pasangan / buku sedemikian sehingga jumlah overhang minimal. Anda tidak boleh memutar buku - saya ingin semua duri menghadap ke arah yang sama. Jika ada beberapa solusi dengan jumlah overhang yang sama, Anda dapat memilih urutan tersebut. Algoritma pengurutan Anda tidak harus stabil. Implementasi Anda dapat mengasumsikan bahwa dimensi buku masing-masing kurang dari 16 .
Kompleksitas waktu: Untuk membuat ini sedikit lebih menarik, kompleksitas kasus terburuk asimtotik algoritma Anda harus polinomial dalam ukuran tumpukan. Jadi Anda tidak bisa hanya menguji setiap permutasi yang mungkin. Harap sertakan bukti singkat tentang optimalitas dan kompleksitas algoritma Anda dan secara opsional plot yang menunjukkan penskalaan untuk input acak besar. Tentu saja, Anda tidak dapat menggunakan ukuran maksimum input sebagai argumen bahwa kode Anda berjalan di O (1).
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN, ARGV atau argumen fungsi dalam format daftar yang mudah (tidak diproses) dan mencetak atau mengembalikan hasilnya.
Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.
Saya yakin bahwa ada solusi polinomial, tetapi jika Anda dapat membuktikan bahwa saya salah, Anda dapat mengirimkan bukti seperti itu alih-alih pengiriman golf. Dalam hal ini, Anda dapat mengasumsikan P ≠ NP . Saya akan menerima bukti yang benar pertama dan memberikan hadiah untuk itu.
Contohnya
In: [[1, 1], [10, 10], [4, 5], [7, 5], [7, 7], [10, 10], [9, 8], [7, 5], [7, 5], [3, 1]]
Out: [[10, 10], [10, 10], [9, 8], [7, 7], [7, 5], [7, 5], [7, 5], [4, 5], [3, 1], [1, 1]]
In: [[4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [5, 4], [4, 5]]
Out: [[4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4]]
or [[5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5]]
In: [[2, 3], [1, 1], [5, 5], [7, 1]]
Out: [[5, 5], [2, 3], [7, 1], [1, 1]]
or [[5, 5], [2, 3], [1, 1], [7, 1]]
or [[7, 1], [5, 5], [2, 3], [1, 1]]
or [[7, 1], [1, 1], [5, 5], [2, 3]]
Saya membuat ini dengan tangan, jadi beri tahu saya jika Anda menemukan kesalahan.
sumber
Jawaban:
Pyth , 30
Ini adalah golf langsung dari algoritma grc yang luar biasa. Berikut ini adalah padanan yang tepat dari program pyth di atas, dalam kode python yang dikompilasi.
Dalam konteks ini,
Psum(Y)
fungsinya setara dengan pythonsum(Y,[])
.Kompilasi dan jalankan kode aktual (dari
pyth -d
):sumber
sum(Y,[])
. Ini semua harus berfungsi dalam Pyth, hanya saja terjemahannya tidak secara otomatis memasukkannya.Pprint("\n",Psum(Y))
. Saya pikir dia mungkin telah menyederhanakannya untuk kenyamanan, bersama dengan semua-1
dll.Psum
Sebenarnya akan berjalan lebih sukareduce(lambda x,y:x+y, Y[1:], Y[0])
.Python, 113
Setelah mengurutkan daftar buku dalam urutan menurun (dengan lebar pertama dan kemudian tinggi), ini membagi buku menjadi tumpukan tanpa tumpang tindih. Untuk menentukan di mana menempatkan setiap buku, tingginya dibandingkan dengan ketinggian buku teratas di setiap tumpukan. Itu ditempatkan di tumpukan pertama mungkin, atau tumpukan baru dibuat.
Saya tidak begitu baik dengan kompleksitas waktu, tetapi saya percaya ini akan memiliki kasus terburuk O ( N 2 ). Ada dua loop, masing-masing dengan paling banyak N iterasi. Saya juga menggunakan jenis builtin Python, yaitu O ( n log n ).
Bukti pertama saya bahwa algoritma ini menghasilkan solusi optimal ternyata salah. Terima kasih banyak kepada @xnor dan @ Sp3000 untuk diskusi hebat dalam obrolan tentang membuktikan ini (yang dapat Anda baca mulai dari sini ). Setelah mencari bukti yang benar, @xnor menemukan bahwa sebagian sudah dilakukan ( teorema Dilworth ).
Berikut ini adalah ikhtisar bukti (kredit ke @ xnor dan @ Sp3000).
Pertama, kami mendefinisikan gagasan antipile, atau antikain, ( dikutip dari @xnor ):
Kemudian, kami mengurutkan buku-buku dalam urutan menurun berdasarkan lebar (pertama) dan tinggi (kedua) *.
Untuk setiap buku B , kami melakukan hal berikut:
Sekarang, kami telah membuat tautan dari setiap buku (kecuali yang ada di tumpukan pertama), ke sebuah buku di tumpukan sebelumnya yang lebarnya lebih besar dan tingginya lebih rendah.
Diagram luar biasa @ Sp3000 menggambarkan hal ini dengan baik:
Dengan mengikuti jalur apa pun dari tumpukan terakhir (di kanan), ke tumpukan pertama (di sebelah kiri), kita mendapatkan antipile. Yang penting, panjang antipile ini sama dengan jumlah tumpukan. Oleh karena itu, jumlah tumpukan yang digunakan adalah minimal.
Akhirnya, karena kami telah mengatur buku ke dalam jumlah minimum tumpukan tanpa tumpang tindih, kami dapat menumpuknya di atas satu sama lain untuk mendapatkan satu tumpukan dengan jumlah minimum tumpang tindih.
* komentar yang bermanfaat ini menjelaskan beberapa hal
sumber