Tantangan
Ada N kota yang diluruskan dalam garis lurus. Kota ke-i terletak beberapa A[i]
kilometer di sebelah kanan asalnya. Tidak ada dua kota di tempat yang sama.
Anda akan membangun jaringan listrik dengan beberapa pembangkit listrik. Pembangkit listrik harus dibangun di dalam kota. Namun, Anda hanya diizinkan untuk membangun K
(<N) pembangkit listrik, sehingga akan ada beberapa kota tanpa pembangkit listrik di dalamnya. Untuk setiap kota tanpa pembangkit listrik, Anda harus membangun kabel di antara itu dan kota terdekat yang memiliki pembangkit listrik .
Misalnya, jika ada tiga kota yang berlokasi di 0, 1, 2
, dan hanya kota yang 0
memiliki pembangkit listrik, Anda perlu membangun dua kabel, satu dari 2
ke 0
(2 km) dan yang lain dari 1
ke0
(1 km), yang memiliki total panjang 3 km .
Diberikan K
dan posisi kota (A
), Anda harus menghitung kilometer minimum kabel yang Anda butuhkan untuk membangun jaringan.
Contoh Testcases
K = 1, A = [0, 2, 4, 6, 8] : 12
# build power plant in the city at position 4, total length = 4 + 2 + 0 + 2 + 4 = 12
K = 3, A = [0, 1, 10, 11, 20, 21, 22, 30, 32] : 23
# build power plants in cities at positions 0, 10 and 22
K = 5, A = [0, 1, 3, 6, 8, 11, 14] : 3
# build power plants in all cities except those at positions 0, 3
K = 6, A = [0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84] : 49
Spesifikasi
Anda harus mengimplementasikan fungsi atau program, yang mengambil bilangan bulat positif
K
dan daftar bilangan bulatA
dalam bentuk apa pun, dan mengeluarkan / mengembalikan bilangan bulat yang mewakili jawabannya.A
diurutkan dalam urutan menaik, dan semua elemen adalah bilangan bulat non-negatif.A[0] = 0
, danA[N-1]
tidak akan lebih dari 1000N.Perhatikan bahwa output akan besarnya 1000N 2 , jadi dalam kasus yang lebih besar, Anda mungkin perlu integer 64-bit dalam beberapa bahasa.
Multithreading tidak diizinkan (saya akan mengatur afinitas program Anda menjadi hanya 1 inti saat menilai). Optimalisasi kompiler (seperti
-O2
dalam C) diizinkan.
Mencetak gol
Saya akan mengatur waktu kode Anda di komputer saya (Ubuntu 16.04 dengan prosesor Intel i7-3770S) dengan ukuran testcases yang berbeda. Secara khusus, saya akan menghasilkan beberapa testcases dengan N = lantai (2 x / 5 ) di mana x adalah bilangan bulat positif.
Skor Anda akan menjadi nilai x dari testcase terkecil yang menggunakan program Anda lebih dari 10 detik atau 1 GiB memori, atau tidak memberikan jawaban yang benar.- Jawaban dengan skor tertinggi menang. Jika dua jawaban mendapatkan skor yang sama, jawaban sebelumnya menang.
Semua program akan dinilai oleh set testcases yang sama.
Jangan ragu untuk memposting skor Anda sendiri. Penjelasan tentang algoritma Anda disarankan.
Bonus
Ini adalah program C ++ saya, skornya 108 . Anda dapat memverifikasi intisari SHA-2569a87fa183bad1e3a83d2df326682598796a216b3a4262c32f71dfb06df12935d
dengan seluruh segmen kode (tanpa catatan kaki) di tautan.
Algoritma ini menggabungkan pencarian biner dan optimasi Knuth untuk menemukan penalti yang tepat dari setiap pabrik untuk mendapatkan angka yang diinginkan. Kompleksitasnya adalah O (N log N log A [N-1]). Saya terkejut bahwa program tersebut mendapat skor lebih tinggi daripada solusi O (N log A [N − 1]) oleh Anders Kaseorg . Mungkin karena fakta bahwa kasus log dalam optimasi Knuth biasanya tidak akan terjadi.
Perhatikan bahwa tantangan ini sama dengan Kantor Pos IOI 2000 . Kendala aslinya adalah N <= 300 dan K <= 30.
sumber
2^^(x/5)
: apa artinya ? bisakah kamu memberikan batas atas untuk N?N=21( = floor(2^(22/5)) )
dalam 10 detik, tetapi tidak dapat menanganiN=24( = floor(2^(23/5)) )
, maka 23 akan menjadi skor. Saya tidak menggunakan batas atas, karena perbedaan antara algoritma yang berbeda terlalu besar. Sebagai contoh, jika saya menetapkan N <= 40, akan ada sedikit perbedaan antaraO(KN^2)
danO(KN^3)
, namunO(2^N)
tidak akan selesai dalam waktu yang beresonansi.Jawaban:
Karat , skor = 104
Ini adalah implementasi dari algoritma yang dicatat oleh Grønlund et al. (2017) pada akhir §3.3.1, meskipun saya harus mengikuti rantai kutipan yang panjang dan mengisi beberapa detail yang hilang. Ini berjalan di O ( N log A [ N - 1]).
Kompilasi dengan
rustc -O
. Format input adaK
di baris pertama, diikuti oleh entri dariA
, satu entri per baris, semua di stdin.(Catatan: Saya mengirimkan ini satu jam setelah batas waktu karunia, tetapi saya mengharapkan versi terakhir yang saya kirimkan sebelum batas waktu karunia , yang berjalan dalam waktu O ( N log N log A [ N - 1]), untuk mencetak skor sekitar 94 .)
Cobalah online!
Karat , skor pretest = 73
Kompilasi dengan
rustc -O
. Format input adaK
di baris pertama, diikuti oleh entriA
, satu entri per baris, semua di stdin.Cobalah online!
sumber
61
, tapi itu karena kelebihanu32
. Mungkin Anda bisa mengubah ke tipe integer 64-bit?type Cost = u32
ketype Cost = u64
?73
.C, skor = 56
isi dari
a.c
:skrip shell untuk mengkompilasi dan menguji hal di atas:
n = 776 mengambil 6.2s, n = 891 mengambil 12sn = 1176 membutuhkan 5.9s, n = 1351 membutuhkan lebih dari 10sn = 1351 membutuhkan 8,7s, n = 1552 membutuhkan lebih dari 10s (dengan k = 2 * n / 3) pada saya
Intel(R) Core(TM) i3-2375M CPU @ 1.50GHz
sumber
syntax/c.vim
.C ++, skor = 53
Solusi yang saya katakan di komentar.
O(n²×k)
. (sekarang saya menghapusnya karena tidak lagi diperlukan) Mungkin dapat dikurangi menjadiO(n×k)
.Input cukup fleksibel, pada baris pertama, angka pertama adalah
k
, angka-angka lainnya adalah item arraya
, tetapi jika bertemu dengan tanda kurung dekat itu berhenti membaca input. Jadi input likeK = 1, A = [0, 2, 4, 6, 8] : 12
diterima.Cobalah online!
Hasilkan kasus uji acak. (input
N
dan rentang kota opsional,1000×N
secara default)sumber
int
s yang diperlukan untukint64_t
s.C #, skor = 23
Saya yakin ini tidak akan memenangkan tantangan ini, saya hanya ingin memposting jawaban pertama (dan sangat mendasar) untuk mendorong orang lain untuk memposting algoritma mereka dan meningkatkan saya. Kode ini harus dikompilasi sebagai proyek konsol yang menggunakan paket Combinatorics dari NuGet. Metode utama berisi beberapa panggilan ke
Build
metode untuk menguji kasus yang diusulkan.Penjelasan benar-benar sederhana: untuk setiap kombinasi
c
darik
unsur-unsur daria
, menghitung jumlah jarak dari setiap elemena
ke elemen terdekat dic
, dan kembali kombinasi dengan total jarak setidaknya.Versi
Build
metode satu-liner (mungkin lebih lambat dari versi asli, diperluas; ini perlu menambahkan referensi keSystem.Linq
):sumber
C ++, skor = 48
Input penggunaan: NKA [1] A [2] ... A [N]
sumber
step
menjadi 70, maka skor pretest Anda adalah 60.Ruby , skor = 23
Cobalah online!
Saya tidak berpikir itu akan menang, tetapi saya ingin mencobanya.
sumber
JavaScript (ES6) (Node.js) , skor = 10
Algoritma Baru, akan menjelaskan apakah itu benar-benar berfungsi saat ini.
Cobalah online!
Jalankan dengan cara yang sama seperti yang lainnya.
JavaScript (ES6) (Node.js) , skor pretest = 12
Garis besar algoritme:
Program pertama-tama memetakan Data ke dalam Kelas Kota, yang memetakan beberapa titik data:
array tersebut kemudian dilemparkan ke dalam kelas Grup, yang memiliki yang berikut:
Sekarang algoritma mulai membagi kelompok-kelompok selama ia memiliki 2 atau lebih pembangkit listrik untuk ditempatkan.
Akhirnya memetakan grup ke pusat itu, dan merangkum semuanya.
Cara menjalankan:
Jalankan menggunakan Node.js (v9.2.0 adalah apa yang digunakan untuk pembuatan)
menjalankan program menggunakan test case yang dihasilkan untuk skor 70:
menjalankan program menggunakan 1 pembangkit listrik dan kota-kota [0,3,5]:
Kode:
Cobalah online!
Saya akan membersihkan kode komentar selama beberapa hari ke depan karena saya masih mengerjakan ini, hanya ingin melihat apakah ini melewati lebih dari sekadar kasing kecil.
sumber
K = 2, A = [0, 21, 31, 45, 49, 54]
. Jawaban yang benar adalah 40, tetapi program Anda menghasilkan 51.K = 2, A = [0, 4, 7, 9, 10]
. Benar: 7, jawaban Anda: 8.K = 2, A = [0, 1, 3, 4, 9]
. Benar: 6, jawaban Anda: 7.C (non-bersaing, skor pretest = 76)
Ini adalah upaya untuk menerjemahkan solusi Rust kedua @ AndersKaseorg ke C.
Kompilasi dengan:
sumber
Bersih , skor = 65
Kompilasi dengan:
clm -h 1024M -gci 32M -gcf 32 -s 32M -t -nci -ou -fusion -dynamics -IL Platform main
Mengambil
K
, dan kemudian setiap elemenA
, sebagai argumen baris perintah.sumber