Karena dalam bentuk ini, para peserta konferensi bertarung dengan mereka dan karena bahasa Inggris adalah bahasa resmi Hydra. Tugasnya terlihat seperti ini:

Mulai pukul 5:53, hanya 4 menit:

Dan inilah bagaimana orang-orang dengan flipchart itu memutuskan keputusan mereka:

Di permukaan, ada solusi seperti itu: jumlah bobot semua replika, hasilkan angka acak dari 0 hingga jumlah semua bobot, lalu pilih replika-i sehingga jumlah bobot replika dari 0 hingga (i-1) kurang dari angka acak, dan jumlah bobot replika dari 0 hingga i-th - lebih dari itu. Ini akan berubah untuk memilih satu replika, dan untuk memilih yang berikutnya, Anda perlu mengulangi seluruh prosedur tanpa mempertimbangkan replika yang dipilih. Dengan algoritma seperti itu, kompleksitas memilih satu replika adalah O (N), kompleksitas memilih replika K adalah O (N · K) ~ O (N ² ).

Kompleksitas kuadrat memang buruk, tetapi bisa diperbaiki. Untuk melakukan ini, buatlah sebuah pohon segmen untuk jumlah bobot. Ini akan menghasilkan pohon dengan kedalaman log N, di mana daun akan ada bobot replika, dan di simpul yang tersisa, jumlah parsial, hingga jumlah semua bobot di akar pohon. Selanjutnya, kami menghasilkan angka acak dari 0 hingga jumlah semua bobot, menemukan replika engan, menghapusnya dari pohon, dan mengulangi prosedur untuk mencari replika yang tersisa. Dengan algoritma seperti itu, kompleksitas membangun pohon adalah O (N), kompleksitas menemukan replika ith dan menghapusnya dari pohon adalah O (log N), kompleksitas memilih replika K adalah O (N + K log N) ~ O (N log N) .

Kompleksitas linear-logaritmik lebih bagus daripada kompleksitas kuadratik, terutama untuk K. besar.

Algoritma ini diimplementasikan dalam kode perpustakaan ClusterClient dari proyek Vostok .

Mulai pukul 34:50, hanya 6 menit:

Solusinya ada di permukaan: urutkan semua dokumen (misalnya, menggunakan quicksort ), lalu ambil dokumen N + S. Dalam hal ini, kompleksitas pengurutan rata-rata adalah O (M lg M), dalam yang terburuk - O (M ² ).

Jelas, menyortir semua dokumen M untuk kemudian hanya mengambil sebagian kecil dari mereka tidak efisien. Agar tidak mengurutkan semua dokumen, algoritma pemilihan cepat cocok , yang memilih N + S dari dokumen yang diperlukan (mereka dapat diurutkan berdasarkan algoritma apa pun). Dalam hal ini, kompleksitas menurun rata-rata menjadi O (M), dan kasus terburuk tetap sama.

Namun, Anda dapat melakukannya dengan lebih efisien - gunakan algoritma streaming biner tumpukan . Dalam hal ini, dokumen N + S pertama ditambahkan ke tumpukan minimum atau maksimum (tergantung pada arah penyortiran), dan kemudian setiap dokumen selanjutnya dibandingkan dengan akar pohon, yang berisi dokumen minimum atau maksimum saat ini, dan ditambahkan ke pohon jika perlu . Dalam hal ini, kompleksitas dalam kasus terburuk adalah ketika Anda harus terus membangun kembali pohon - O (M lg (N + S)), kompleksitas rata-rata adalah O (M), seperti pemilihan cepat.

Namun, heap streaming lebih efektif karena pada kenyataannya sebagian besar dokumen dapat dibuang tanpa membangun kembali heap, setelah perbandingan tunggal dengan elemen rootnya. Pemilahan semacam itu diimplementasikan dalam basis data dalam dokumen Zebra yang dikembangkan dan digunakan dalam Sirkuit.

Solusi di permukaan: bertukar status elemen pertama dan kedua, lalu yang pertama dan ketiga, lalu yang pertama dan keempat, dan seterusnya. Setelah setiap pertukaran, keadaan satu elemen akan berada pada posisi yang diinginkan. Anda harus melakukan permutasi O (N) dan menghabiskan waktu O (N · M).

Waktu linier adalah waktu yang lama, sehingga Anda dapat bertukar status elemen berpasangan: yang pertama dengan yang kedua, yang ketiga dengan yang keempat, dan seterusnya. Setelah setiap pertukaran, keadaan setiap elemen kedua akan berada di posisi yang diinginkan. Kita harus melakukan permutasi O (log N) dan menghabiskan waktu O (M log N N).

Namun, Anda dapat membuat perubahan lebih efektif - tidak dalam linier, tetapi dalam waktu yang konstan. Untuk melakukan ini, pada langkah pertama, Anda perlu bertukar keadaan elemen pertama dengan yang terakhir, yang kedua dengan kedua dari belakang, dan seterusnya. Keadaan elemen terakhir akan berada pada posisi yang diinginkan. Dan sekarang Anda perlu menukar status elemen kedua dengan elemen terakhir, ketiga dengan kedua dari belakang, dan seterusnya. Setelah putaran pertukaran ini, keadaan semua elemen akan berada di posisi yang tepat. Secara total, permutasi O (2M) ~ O (1) akan dilakukan.

Solusi seperti itu tidak akan mengejutkan seorang ahli matematika yang masih ingat bahwa rotasi adalah komposisi dari dua simetri aksial. Ngomong-ngomong, ini digeneralisasi secara sepele untuk bergeser bukan oleh satu, tetapi oleh posisi K <N. (Tulis di komentar bagaimana persisnya.)