Pendahuluan
Sudah pada Oktober 2018, kami dengan senang hati mengingat kalender Advent dengan tugas-tugas 2017 (kondisinya di
sini ) dan mulai berpikir tentang apa yang dapat dilakukan tahun ini. Dari beberapa ide yang layak, kami memilih opsi di mana kami memilih beragam tugas "menarik", disatukan oleh kisah Tahun Baru yang indah.
Tidak ada yang tersisa: sebenarnya, mengambil tugas, menulis cerita, membuat situs web dengan papan peringkat, cantik dan erat dengan Yandex.Constest, dan mulai pada awal Desember :-)
Hasil
Seperti yang Anda ketahui, nafsu makan datang bersamaan dengan makan, dan kami langsung terjun ke dalam proses mencari tahu isi tugas dan penerapan teknisnya. Setiap temuan yang berhasil menginspirasi perbaikan lebih lanjut. Akibatnya, kami mengangkat server terpisah untuk salah satu tugas, menjadikan yang lain sebagai pengoptimalan (kami masih belum memiliki jawaban yang tepat), merekam musik sendiri, memulihkan distribusinya - kami sama sekali tidak bosan!
Hasilnya adalah:
- 11 tugas (+1 bonus) dengan berbagai kesulitan, semuanya dengan verifikasi dalam Kontes;
- situs eksternal untuk peserta ;
- 11 hari (dari 7 Desember hingga 17 Desember inklusif) untuk menyelesaikan masalah.
Fakta dan cerita menarik
780 peserta terdaftar, 333 orang mulai menyelesaikan, 203 orang berhasil lulus setidaknya dua tugas.
Awalnya, kami memperkirakan waktu bersih untuk menyelesaikan semua masalah pada tujuh hari untuk peserta yang tidak siap dan dua hari untuk yang sangat berpengalaman (alias lulusan pusat CS baru). Asisten pertama Santa Claus yang dengan benar menyelesaikan semua sebelas tugas diselesaikan sekitar satu hari, dua lagi berhasil yang kedua!
Surat dari salah satu peserta: “Selamat siang! Karena kontes Anda, saya menghentikan kantor (40 orang) khususnya tugas kedua tentang kopi Santa Claus, tolong beri saya petunjuk. Kami semua sangat tersiksa. ”
Mengurai tugas
Ketentuan di
sini .
Tugas D "Pesan Musik" (Mikhail Plotkin)Sangat sederhana untuk menyelesaikan masalah, memiliki pendidikan musik yang minimal.
Upaya untuk menemukan petunjuk dalam pola ritmis tidak mengarah pada kesuksesan. Gagasan berikutnya adalah duduk di depan piano dan mengambil nada yang Anda dengarkan. Ternyata la, lakukan, mi, si, la, ulang, garam, mi. Dalam treble clef seperti ini:
Setelah tiga not pertama, jeda singkat diikuti, seolah-olah membagi frasa musik menjadi dua kata. Tinggal menulis catatan dalam notasi huruf tradisional (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = garam) dan dua kata dibuka: ACE BADGE.
Tanpa pengetahuan tentang melek musik, memecahkan masalah lebih sulit. Misalnya, seseorang dapat menggunakan beberapa program untuk memproses suara dan mencari tahu catatan itu sendiri atau frekuensi suara di hertz, dan kemudian mencari tahu frekuensi mana yang sesuai dengan catatan mana.
Tugas yang diperlukan untuk menulis surat bersama tanpa pemisah, jadi jawabannya adalah ACEBADGE.
Tugas F "Tas Kepingan Salju" (Mikhail Plotkin)Luas segitiga awal adalah 1. Selanjutnya, pada langkah ke - n , segitiga t_n ditambahkan, masing-masing memiliki luas s_n. Total area dari gambar yang dihasilkan dinyatakan sebagai jumlah dari deret tak hingga:
S = 1 + Σ (t_n * s_n), jumlah lebih dari n adalah dari 0 hingga ∞ (1)
Pada langkah nol, t_0 = 3, s_0 = 1/9, karena segitiga memiliki 3 sisi, di mana masing-masing segitiga dibangun dengan sisi 3 kali lebih kecil dari aslinya, dan oleh karena itu area 9 kali lebih kecil dari luas segitiga asli.
Pada setiap langkah selanjutnya, setiap sisi berubah menjadi 4 sisi, tiga kali lebih kecil, yaitu
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n.
Oleh karena itu, area yang diperlukan:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n), jumlah di atas n adalah dari 0 hingga ∞ (2)
Istilah kedua adalah jumlah dari perkembangan geometrik yang menurun tanpa batas. Untuk menghitungnya, gunakan rumus sekolah
Σ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5.
Mengganti dalam rumus (2), kita mendapatkan jawabannya:
S = 1 + 1/3 * 9/5 = 8/5 = 1.6
Tugas G dan L “Rute dibangun” (Artyom Romanov)Terima kasih kepada Artyom
mehrunesartem untuk solusinya! Omong-omong, grafik yang digunakan dalam Masalah G didasarkan pada London Underground :)
Untuk mengatasi masalah ini, kami akan menggunakan versi modifikasi dari pencarian luas pertama. Kami mendapatkan vertex imajiner (sumber), dari mana kami menggambar tepi nol berat pada setiap vertex grafik. Setiap negara secara unik ditentukan oleh jalur yang dilewati dari sumber. Selain itu, kami akan menyimpan waktu yang dihabiskan dan sukacita yang diterima.
Kami memulai antrian prioritas dengan ukuran tetap, di mana kami akan menempatkan status. Sebagai penilaian kondisi dalam antrian, kami akan menggunakan rasio kebahagiaan yang diterima dengan waktu yang dihabiskan. Penilaian ini tidak benar, tetapi menunjukkan hasil yang baik dalam tugas ini.
Pada setiap langkah, kita akan mendapatkan negara dengan estimasi terbaik dari antrian dan menempatkan negara yang terbentuk darinya dalam antrian. Dengan pendekatan ini, akan butuh waktu lama untuk mendapatkan hasil akhir.
Untuk mempercepat solusinya, kami akan mencari jawabannya secara bertahap. Pada setiap langkah, untuk mencari simpul berikutnya di jalur, kami akan menghapus antrian dan menempatkan status saat ini di dalamnya. Kemudian kita akan membuat sejumlah langkah tetap, secara bersamaan memperbarui keadaan yang memberikan banyak kesenangan. Sebagai vertex berikutnya dari path, kita mengambil vertex berikut vertex terakhir dari state saat ini di path dari state yang dihasilkan yang memberikan jumlah kesenangan terbesar. Kami mengulangi tindakan yang dilakukan hingga kami dapat meningkatkan kondisi saat ini.
Kemungkinan peningkatan
- Gunakan heuristik terbaik.
- Dengan implementasi algoritma ini, status tambahan akan muncul, karena pada setiap langkah kami akan menambahkan semua status yang bisa berasal dari yang saat ini. Untuk mencegah hal ini, dengan menggunakan algoritma Dijkstra, untuk setiap simpul grafik, pertama-tama Anda dapat membuat pohon jalur terpendek ke semua simpul lainnya dan membuat transisi tidak dalam satu langkah, tetapi di sepanjang pohon yang dibangun hingga kami mencapai simpul yang belum pernah kami kunjungi.
Perubahan-perubahan ini tidak memberikan perbaikan yang signifikan, kemungkinan besar karena fakta bahwa hanya ada satu tes tertutup, dan bukan kelompok tes yang dihasilkan berbeda.
Tugas I “Beruang-digitizers” (Alexander Samofalov)Mari kita lihat
kode sumber layanan .
Daftar semua id yang tersedia bagi pengguna dapat diperoleh di
/data .
Jika ada id, maka data dapat diperoleh dengan menggunakan permintaan ke alamat
/data/id .
Untuk mengakses data, layanan memerlukan token untuk otentikasi. Kami memiliki
token yang tersedia, tetapi telah kedaluwarsa dan layanan tidak lagi menerimanya.
Mari kita lihat dalam kode
bagaimana token ini dihasilkan . Token diperoleh dengan mengenkripsi JSON dari formulir
{ “userId” : “id”, expireDate: “date”} dan kemudian menyandikannya di base64. Layanan menggunakan RSA untuk enkripsi, dan kunci publik dapat diperoleh dengan permintaan di
/key .
Mari kita membuat permintaan: e = 30593, n = 66043. Sejak n cukup kecil, maka kita dapat dengan mudah menghitung kunci privat.
Untuk melakukan ini, kami menguraikan dan menjadi faktor utama: 211 * 313.
Kami menghitung
fungsi Euler dari n: φ (n) = (211 - 1) (313 - 1) = 65520.
Kami mendapatkan d = e-1 (mod φ (n)) = 257.
Modulo elemen terbalik dapat dihitung dengan menggunakan
algoritma Euclidean canggih .
Setelah menghitung kunci pribadi, kami mendekripsi token yang tersedia bagi kami.
Kami mendapatkan JSON berikut:
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}Perhatikan bahwa itu sudah
cukup untuk layanan bagi pengguna dengan userId yang diberikan ada dan kadaluwarsa kurang dari waktu saat ini di server.
Yaitu, mengetahui userId, kita dapat menghasilkan token baru yang valid.
Untuk melakukan ini, ambil expireDate yang cukup besar untuk lulus tes - misalnya
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} .
Kami mengenkripsi token baru kami menggunakan kunci publik.
Setelah mengajukan permintaan ke
/data , kami mengetahui bahwa pengguna membuat pesan dengan pengidentifikasi dari 1 hingga 4.
Kami akan memilah mereka semua.
Di antara mereka ada ungkapan yang indah:
Tahun Baru mengetuk pintu, segera buka! .
Kiat untuk memecahkan beberapa masalah lain (dari Artyom Romanov)Tugas A "Aman dengan huruf"Anda mungkin memperhatikan bahwa setiap dua puluh langkah Anda akan mendapatkan nomor yang sama.
Tugas B "Rahasia Profesor"Urutkan kata-kata dalam urutan popularitas yang menurun. Anda mungkin memperhatikan bahwa setiap kata berikutnya muncul kira-kira 2, 3, 4, dll. kali lebih sedikit dari kata yang paling populer. Sekarang Anda dapat mengembalikan jawabannya.
Tugas C “Bencana Komputer”Pikirkan bahasa pemrograman Whitespace.
Tugas J "Bengal"Kemungkinan penempatan:
Masalah K "Pola Frosty"Untuk mengatasi masalah ini, Anda dapat memilih segitiga praktis, misalnya yang tepat, dan menghitung jawabannya.
Ucapan Terima Kasih
Seluruh proses dari ide hingga implementasi didorong dan dikoordinasikan oleh Katya Lebedeva. Katya Artamonova, Alina Mozhina, Sasha Komissarov dan saya membantunya menyelesaikan tugas. Lyosha Tolstikov menulis tiga catur kompleks, Sasha Komissarov dan Seryozha Zherevchuk membuat server, Svyato dan Seryozha tanpa pamrih membuat situs web yang indah dengan integrasi yang erat dengan tugas: setiap peserta dapat melihat kemajuan dan papan peringkatnya.