Ini adalah tantangan yang semula merupakan tas untuk Bundatik Jerman Informatik (kompetisi federal ilmu komputer [?]), Kompetisi untuk siswa sekolah menengah. Berbeda dengan pertanyaan awal, di mana Anda harus menemukan solusi yang baik dan menulis beberapa dokumentasi, saya ingin Anda bermain golf ini. Saya mencoba mereplikasi pertanyaan sebaik mungkin:
Tantangan
Banyak kota di Eropa memiliki apa yang disebut kota kembar . Tahun ini, ada Jubilee khusus di mana setiap pasangan kota kembar di UE menyelenggarakan festival untuk merayakan kemitraan mereka. Untuk memastikan bahwa tidak ada kota yang menyelenggarakan terlalu banyak festival, setiap kota memiliki batas festival yang dapat diorganisir. Mungkinkah untuk mendistribusikan festival di antara kota-kota kembar sedemikian rupa, sehingga setiap pasangan kota kembar menyelenggarakan satu festival di satu kota dua dan tidak ada kota yang menyelenggarakan lebih banyak festival daripada yang diizinkan? Jika ya, jelaskan caranya.
Ini adalah peta dari beberapa kota, kemitraan mereka dan batasan festival mereka.
kemitraan http://dl.dropbox.com/u/1869832/partnerships.png
Persyaratan
- Program Anda harus mengakhiri masalah dalam satu menit masing-masing untuk kedua testcases. (Lihat di bawah)
- Lihat testcases untuk format input.
Outputnya harus kosong jika tidak ada solusi dan harus memiliki format berikut: Jika tidak, satu baris untuk setiap pasangan kota kembar,
a
jikacity1
menyelenggarakan festival,b
sebaliknya.<city1>, <city2>, <a/b>
Solusi dengan jumlah karakter paling sedikit yang memenuhi persyaratan menang. Dalam kasus seri, program yang diajukan menang terlebih dahulu.
- Aturan golf-aturan biasa berlaku.
Testcases
Tugas asli memiliki dua testcases. Saya telah mengunggahnya di github .
sumber
n
simpul, di manan
batas anggaran kota).Jawaban:
Python, 380 karakter
Kode ini menggunakan algoritma aliran maksimum push-relabel -style .
N[x]
adalah jumlah pihak yang diizinkan padax
,X[x]
adalah daftar kota mitra yang saat ini dijadwalkan untuk dihosting dix
(yang mungkin lebih lama daripadaN[x]
selama algoritma), danH[x]
merupakan ketinggian berlabelx
. Untuk kota yang berlangganan berlebih, kami mendorong salah satu pihak yang dijadwalkan ke kota mitra yang lebih rendah, atau menaikkan tinggi.sumber
C #,
1016 992916 karakterMembutuhkan 4 detik untuk saya di set tes besar; kinerja dapat dengan mudah ditingkatkan banyak dengan membuat
X
sebuahHashSet<s>
daripadaList<s>
.Ini menggunakan reduksi ke aliran maks yang saya sebutkan sebelumnya di komentar. Verteksnya adalah
S
dan wastafel yang baru dibuatT
.Tepinya adalah
Algoritma ini adalah Ford-Fulkerson dengan DFS. Jelas apriori bahwa setiap jalur penambahan akan meningkatkan aliran sebesar 1, sehingga optimalisasi golf untuk menghilangkan perhitungan aliran jalur tidak memiliki efek negatif pada kinerja.
Ada kemungkinan optimisasi lain dengan membuat asumsi seperti "Nama file input tidak akan pernah sama dengan nama kota", tapi itu IMO agak rapuh.
sumber