kactl

KACTL

Repo ini menampung KACTL, dokumen referensi tim ICPC KTH. Terdiri dari 25 halaman kode C++ yang dapat disalin dan ditempel, untuk digunakan dalam kompetisi pemrograman bergaya ICPC.

Lihat kactl.pdf untuk versi final yang dapat dijelajahi, dan content/ untuk kode sumber mentah.

Aspirasi

Algoritme KACTL harus: berguna, singkat, cukup cepat, teruji dengan baik, dan jika relevan, dapat dibaca dan mudah dimodifikasi. Mereka tidak boleh terlalu umum, karena kode diketik secara manual dan itu hanya menambah overhead. Karena masalah ruang, kami juga mengecualikan algoritma yang sangat umum/sederhana (misalnya, Dijkstra), atau sangat tidak umum (pencocokan berbobot umum).

Jika Anda merasa ada sesuatu yang hilang, perlu dibersihkan, atau melihat ada bug, silakan ajukan masalah atau kirim permintaan penarikan!

Menyesuaikan KACTL

Meskipun KACTL dapat digunakan apa adanya, KACTL juga mudah untuk dimodifikasi jika Anda ingin membuat salinan yang dipersonalisasi. Secara khusus, Anda mungkin ingin mengubah halaman sampul, atau menentukan sendiri algoritme yang akan disertakan -- karena masalah ruang, tidak semua algoritme dalam repo disertakan dalam pdf. Anda mungkin juga ingin mengaktifkan penyorotan sintaksis berwarna.

content/kactl.tex adalah file utama KACTL, dan dapat diedit untuk mengubah nama tim, logo, penyorotan sintaksis, dll. Ini mengimpor file chapter.tex dari masing-masing content/ subdirektori, yang menentukan konten setiap bab. Ini termasuk kode sumber, teks dan matematika dalam bentuk LaTeX. Untuk menambah/menghapus kode dari sebuah bab, tambahkan/hapus baris kactlimport yang sesuai dari file chapter.tex . Untuk penyelarasan yang lebih baik, Anda mungkin ingin memasukkan perintah hardcolumnbreak , columnbreak atau newpage , meskipun ini biasanya hanya dilakukan sebelum kontes penting, dan bukan pada cabang utama. Algoritme yang tidak disertakan dalam pdf dibiarkan dikomentari di chapter.tex .

Untuk membuat KACTL, ketik make kactl (atau make fast ) pada mesin *nix -- ini akan memperbarui kactl.pdf . (Windows mungkin berfungsi juga, namun belum diuji.) doc/README memiliki beberapa catatan lagi mengenai hal ini.

Kiat:

1. Periksa apa yang dikecualikan secara default dengan menjalankan make showexcluded . Konfigurasi default dipilih agar menjadi keseimbangan yang wajar bagi pemula dan tim tingkat lanjut.
2. Manfaatkan hashing saat mengetik algoritma ini. Setiap algoritma memiliki hash MD5 6 karakter di kanan atas. Hash ini dapat dihasilkan dengan menggunakan hash.sh atau perintah :Hash dari .vimrc . Hashing mengabaikan spasi dan komentar.

Gaya pengkodean

KACTL menggunakan gaya pengkodean yang relatif singkat, dengan beberapa makro/typedef yang ditentukan dalam templat yang membantu mempersingkat kode. Lebar garis 63 karakter, dengan tab untuk lekukan (tab = 2 spasi di pdf).

Setiap algoritme berisi header dengan pembuat kode, tanggal penambahannya, deskripsi algoritme, status pengujiannya, dan sebaiknya juga sumber, lisensi, dan kompleksitas waktu.

kactl.pdf harus disimpan hingga 25 halaman + halaman sampul. Kadang-kadang kactl.pdf yang dihasilkan dikomit ke repo demi kenyamanan, namun jangan terlalu sering karena membuat operasi git lebih lambat.

Pengujian

KACTL bertujuan untuk mencapai tingkat keyakinan yang tinggi terhadap kebenaran algoritma. Pengujian dilakukan pada juri online dan (untuk algoritma yang lebih baru) dengan stress test yang membandingkan keluaran dengan algoritma yang lebih naif untuk sejumlah besar kasus yang dihasilkan secara acak. Pengujian ini berada di direktori stress-tests , dan dijalankan dengan CI pada setiap penerapan. CI juga memverifikasi bahwa semua header dikompilasi (kecuali untuk daftar pengecualian di docs/scripts/skip_headers ) dan lateks dikompilasi.

old-unit-tests berisi beberapa unit test yang rusak, terakhir disentuh sekitar sepuluh tahun yang lalu.

Lisensi

Seperti biasa untuk program kompetitif, situasi perizinannya agak tidak jelas. Banyak file sumber ditandai dengan lisensi (kami mencoba menggunakan CC0), namun banyak juga yang tidak. Namun, agaknya niat baik diharapkan dari penulis lain, dan dalam banyak kasus, izin tidak diperlukan karena kode tersebut tidak didistribusikan. Untuk membantu melacak kembali, sumber dan penulis dicatat dalam file sumber.

Segala sesuatu dalam stress-tests secara implisit adalah CC0, kecuali implementasi referensi yang diambil dari seluruh Internet.