Pada tanggal 1 Juni, final kejuaraan pemrograman kami berlangsung. Nama-nama pemenang sudah diketahui. Segera mereka akan menerima penghargaan mereka, dan sementara itu, kami mulai mempublikasikan analisis tugas-tugas kejuaraan. Pertama, kami akan menganalisis tugas tahap kualifikasi di antara pengembang backend.
Kualifikasi berlangsung seminggu, dan jumlah peserta dalam ribuan, jadi mempersiapkan tugas, ternyata, bukanlah tugas yang mudah. Secara total, kami harus melakukan 24 tugas dan membaginya di antara empat opsi sehingga opsi tersebut sebanding dalam kompleksitasnya.
Kali ini kami menghasilkan enam tugas, yang masing-masing memungkinkan untuk menghasilkan beberapa formulasi alternatif: satu tugas yang diciptakan memunculkan empat tugas sekaligus! Dengan demikian, opsi-opsi tersebut ternyata sebanding sebanyak mungkin.
Karena itu, saya tidak akan mempublikasikan analisis dari semua 24 masalah. Sebaliknya, saya akan menganalisis enam tugas dari salah satu opsi kualifikasi: yang lain diselesaikan dengan cara yang sama.
A. Alarm
Kondisi tugasBekerja di sebagian besar perusahaan IT memiliki banyak keuntungan: tidak ada kode berpakaian, Anda kadang-kadang dapat bekerja dari jarak jauh, sejuk dan sejawat, dan, tentu saja, jadwal gratis! Namun, jadwal gratis dan kemampuan untuk bekerja jarak jauh membutuhkan banyak kemauan.
Programmer Alexei suka bekerja di malam hari dan tidak suka datang terlambat. Untuk bangun tepat di pagi hari, Alexey memulai setiap malam N alarm di ponsel Anda. Setiap jam alarm diatur sehingga berdering setiap X menit dari titik waktu di mana dia membawa. Misalnya, jika alarm diatur pada suatu titik waktu ti maka dia akan menelepon sesekali ti , ti+X , ti+2 cdotX dll. Pada saat yang sama, jika ada dua alarm mulai berdering pada satu saat, maka hanya satu yang ditampilkan.
Diketahui bahwa sebelum bangun tidur, Alexey mendengarkan setiap pagi K jam alarm, setelah itu bangun. Tentukan titik waktu ketika Alex bangun.
Semua alarm berdering pada waktu integer, dan semua alarm memiliki periode tunda panggilan yang sama. Jika dua alarm diatur pada titik waktu ti dan tj , dan titik waktu ini memberikan sisa yang sama saat dibagi oleh X , Anda hanya dapat meninggalkan satu jam alarm - yang berdering lebih dulu.
Jadi langkah pertama adalah untuk menghilangkan alarm yang tidak perlu: kita akan mengelompokkannya berdasarkan nilai sisa dari divisi dengan X dan dari masing-masing grup kami hanya akan meninggalkan satu jam alarm yang diset pada waktu yang paling awal.
Sekarang kita akan belajar bagaimana menentukan berapa banyak alarm berbunyi pada titik waktu tertentu T . Jika alarm diatur tepat waktu ti , jumlah panggilannya pada saat itu T akan sama
max Besar( fracT−tiX,0 Besar).
Menambahkan nilai-nilai ini untuk semua alarm, kami mendapatkan jumlah total alarm dering berdasarkan waktu T .
Setelah itu, masalah awal diselesaikan dengan pencarian biner oleh T : dengan peningkatan T jumlah alarm dering tidak berkurang (mis. fungsinya monoton); Anda dapat memilih 0 sebagai batas kiri awal, dan jawaban maksimum yang mungkin ada dalam masalah di sebelah kanan.
B. Turnamen olahraga
Kondisi tugasKetika Masha sedang berlibur, rekan-rekannya menyelenggarakan turnamen catur di sistem Olimpiade. Selama istirahat, Masha tidak terlalu memperhatikan usaha ini, jadi dia hampir tidak dapat mengingat siapa yang bermain dengan siapa (tentang urutan permainan, tidak ada pertanyaan). Tiba-tiba, Masha mendapat ide bahwa akan menyenangkan untuk membawa suvenir dari liburan ke pemenang turnamen. Masha tidak tahu siapa yang memenangkan pertandingan terakhir, tetapi dia dapat dengan mudah mengetahui siapa yang bermain di dalamnya, jika saja dia benar mengingat pasangan yang bermain. Bantu dia memeriksa apakah ini masalahnya dan mengidentifikasi calon yang mungkin untuk pemenang.
Masalah ini dapat diatasi dengan mengembalikan grafik game turnamen. Untuk memulainya, jelas bagi setiap peserta tahap turnamen yang telah ia capai: ini ditentukan oleh jumlah pertandingan dengan partisipasinya.
Setelah itu, Anda dapat mendistribusikan game dalam tur. Katakanlah, di semua permainan di babak pertama, salah satu peserta lepas landas di babak pertama, dan yang lain lepas landas lebih awal dari pada yang kedua. Saat memproses permainan tur dengan angka x perlu untuk memeriksa bahwa semua peserta dalam game ini saat ini memainkan jumlah permainan yang sama dengan nomor tersebut x kalau tidak turnamen tidak valid.
Setelah memulihkan skema turnamen, hanya tersisa untuk mencetak jawabannya.
C. Game yang menarik
Kondisi tugasPetya dan Vasya memainkan permainan yang menarik. Pertama, Vasya mengumumkan berapa banyak poin yang Anda butuhkan untuk skor agar permainan berakhir. Kemudian Petya mengambil kartu-kartu tempat bilangan bulat non-negatif ditulis, dan mulai meletakkannya di atas meja satu per satu. Jika ada kelipatan lima pada kartu, maka Vasya mendapat satu poin. Jika ada kelipatan tiga pada kartu, maka satu poin mendapat Petya. Jika ada nomor pada kartu yang bukan kelipatan tiga atau lima, atau sebaliknya, kelipatan keduanya, maka tidak ada yang mendapat poin.
Segera setelah salah satu peserta mendapatkan jumlah poin yang disebutkan Vasya di awal permainan, permainan berhenti dan pemain ini menjadi pemenang. Jika tidak ada peserta yang mencetak jumlah poin yang diperlukan, tetapi pada saat yang sama semua kartu berakhir, maka pemain dengan poin terbanyak dianggap sebagai pemenang. Jika semua kartu sudah habis, dan poin dibagi sama rata, maka undian dinyatakan.
Petya dan Vasya kadang-kadang terburu-buru, sehingga mereka tidak ingin memainkan permainan sepenuhnya, tetapi segera mencari tahu siapa yang akan menang dengan data awal yang diketahui. Mereka meminta Anda untuk menulis sebuah program yang akan membantu menjawab pertanyaan ini.
Hal terpenting dalam tugas ini adalah memahami dengan benar dari kondisi pemain mana dan berapa banyak poin yang diberikan setelah setiap gerakan baru, dan juga dalam kondisi apa pemain memperolehnya.
Masalahnya diselesaikan secara langsung. Karena batasannya lebih dari lembut, itu sudah cukup untuk melewati data sekali, mengganggu pemrosesan mereka, jika salah satu pemain pada langkah berikutnya mencetak jumlah poin yang diperlukan. Jika jumlah minimum poin yang dibutuhkan belum dicetak oleh salah satu pemain, pemenang ditentukan di akhir siklus.
Dalam beberapa versi tugas ini, perlu untuk lebih lanjut menangani situasi di mana pemain dapat menerima poin pada saat yang sama untuk kartu yang sama.
Tugas ini diharapkan yang paling mudah di antara semua tugas kualifikasi.
D. Penganalisis Pengecualian
Kondisi tugasKami menggambarkan sintaksis bahasa pemrograman EX :
func f() {...} - deklarasi fungsi (dalam kurung - badan)maybethrow Exc adalah perintah yang bisa melempar pengecualian tipe Exc , atau mungkin tidak melempar.try {...} suppress Exc - jika pengecualian tipe Exc terjadi di dalam blok ini, maka itu ditekan.f() adalah panggilan ke f .
Dalam bahasa EX semua instruksi, kecuali deklarasi fungsi, hanya bisa berada di badan fungsi. Fungsi tidak dapat dideklarasikan di dalam fungsi lain. Suatu fungsi dapat dipanggil sebelum didefinisikan, juga dalam tubuhnya sendiri. Nama fungsi dan pengecualian dalam bahasa EX harus cocok dengan persamaan reguler [a−zA−Z0−9 ]+ , unik dan tidak cocok dengan kata kunci func , try , suppress , maybethrow .
Program dalam bahasa adalah input EX dan angka x . Untuk setiap fungsi program, tidak lebih dari x pengecualian yang mungkin terbang keluar darinya. Haruskah output x pengecualian terkecil secara leksikografis.
Tugas ini ternyata menjadi yang paling sulit dari semua tugas kualifikasi.
Untuk mengatasinya, dimungkinkan untuk menguraikan program secara sintaksis dengan membuat grafik pemanggilan fungsi: pada grafik ini, setiap fungsi berhubungan dengan sebuah simpul, dan pada pemanggilan fungsi, suatu tepi. Setelah itu, perlu untuk mengimplementasikan secara langsung logika distribusi pengecualian di seluruh grafik - untuk ini, grafik traversal lebar cocok.
Kami akan memilih beberapa pengecualian dan semua fungsi yang dapat memunculkannya. Fungsi-fungsi ini dipanggil dari fungsi lain; mungkin panggilan ada di dalam blok try {...} suppress - dalam hal ini pengecualian tidak berlaku untuk fungsi di mana panggilan terjadi. Dengan demikian, dimungkinkan untuk menentukan semua fungsi dari mana pengecualian ini dapat dilemparkan dengan menggunakan traversal lebar grafik.
Setelah bypass dilakukan untuk semua pengecualian yang mungkin, tetap hanya untuk membentuk jawaban.
E. Decoding
Kondisi tugasLayanan baru telah muncul di Internet. Sayangnya, dia tidak memiliki dokumentasi. Secara empiris, string s diterima dari server. Namun, beberapa karakter di baris ini disandikan - untuk mendapatkan jawaban yang nyata, Anda perlu men-decode baris ini beberapa kali. Karena tidak ada dokumentasi untuk layanan ini, untuk percobaan lebih lanjut perlu ditentukan berapa kali maksimum baris ini dapat diterjemahkan dengan cara yang tidak sepele. Prosedur decoding adalah sebagai berikut: Anda perlu menemukan semua substring dari formulir ~XY , di mana X dan Y adalah digit heksadesimal besar atau kecil dan menggantinya secara bersamaan dengan karakter dengan kode ASCII 16X+Y (setiap substring memiliki sendiri). Decoding disebut sepele jika tidak ada substring semacam ini.
Dalam satu baris cetak jumlah maksimum decodings non-trivial berturut-turut dari string asli.
Kami akan mempertimbangkan karakter string sumber secara berurutan, dari kiri ke kanan. Jika menambahkan karakter lain menghasilkan urutan yang dapat diterjemahkan, Anda perlu melakukan ini. Decoding harus diulang selama mungkin, mis. sementara pada akhir baris saat ini ada urutan bentuk yang ditentukan oleh kondisi tugas.
Untuk setiap karakter dari string yang diterjemahkan, Anda harus ingat berapa kali untuk mendapatkannya Anda harus men-decode string yang asli. Jelas bahwa karakter yang ditambahkan ke string diterjemahkan nol kali. Jika simbol yang didekodekan ambil bagian dalam operasi decoding berikutnya r1,r2,...,rk kali, maka simbol yang mereka bentuk membutuhkan maks(r1,r2,...,rk)+1 operasi decoding.
Biarkan string yang diterjemahkan terakhir berisi karakter a1,...,ak , untuk mendapatkan yang perlu dilakukan decoding, masing-masing, r1,...,rk kali. Maka jawabannya adalah kuantitas
maks(r1,...,rk).
F. Menemukan komit melanggar
Kondisi tugasYandex Search mengimplementasikan kebijakan yang disebut "trunk hijau": kode apa pun yang memasuki repositori, dengan beberapa peringatan, dijamin tidak akan merusak perakitan dan pengujian.
Namun, tes sangat sulit, dan menjalankan semuanya pada setiap komit tidak praktis. Jadi untuk kasus-kasus yang sangat sulit, prosedur berikut diimplementasikan: tes dijalankan dengan beberapa keteraturan, dan serangkaian komitmen diperiksa segera. Dengan demikian, untuk beberapa waktu n komit yang belum diuji dapat jatuh ke dalam bagasi, di antaranya setidaknya satu berisi kesalahan.
Dalam situasi seperti itu, sistem pengujian harus mendeteksi angka m dari komit pertama yang memecahkan tes. Angka ini memiliki properti berikut: semua berhasil dengan angka kurang dari tes lulus m, dan berkomitmen dengan angka lebih besar dari atau sama dengan tes gagal m. Tugas memastikan bahwa komit dengan properti yang ditentukan harus ada dan unik.
Untuk menghemat sumber daya, sistem pengujian hanya dapat memeriksa satu komit pada satu waktu. Anda perlu menulis program yang akan menentukan angka m.
Tugas ini memiliki prototipe dalam produksi kami: beberapa pengujian komponen pencarian benar-benar terlalu rumit, terlalu mahal untuk dijalankan untuk setiap komit, dan bagi mereka prosedur untuk menemukan gangguan yang serupa dengan yang dijelaskan dalam tugas diimplementasikan. Tentu saja, pengembang dapat menggunakan verifikasi pra-audit dan, sebagai aturan, melakukan ini, sehingga prosedur ini tidak begitu sering diperlukan.
Versi tugas yang berbeda berbeda dalam jumlah komit yang perlu diperiksa pada saat yang sama.
Solusinya di sini cukup sederhana: Anda perlu menerapkan versi pencarian biner yang sedikit lebih kompleks. Katakanlah, jika Anda ingin memeriksa empat komit sekaligus, Anda perlu membagi segmen saat ini secara merata dengan empat angka. Selama implementasi, beberapa kehati-hatian harus dilakukan untuk menghindari loop ketika panjang segmen kurang dari jumlah komitmen diperiksa secara bersamaan. Perlu juga dicatat bahwa, sesuai dengan kondisi masalah, Anda dapat memeriksa komit yang sama beberapa kali - kadang-kadang Anda harus melakukan ini, misalnya, jika ada dua total komitmen, dan Anda perlu memeriksa tiga komit sekaligus.
Putaran tugas kualifikasi yang dibahas tersedia sebagai pelatihan Codeforces . Kami juga melakukan pelatihan tentang tugas-tugas final .