Buat TOC sudah menjadi salah satu impianku setelah TOC diadakan bulanan. Aku bahkan sudah ada ide beberapa soal. Namun, karena pengetahuanku masih minim, aku jadikan itu rencana jangka panjang. Diluar rencana, ada dua kejadian yang membuat rencanaku dipercepat, Pertama karena aku mau buat essay kuliah, terus mentorku bilang kalau essayku gaada menunjukkan sifat kolaborasi dan yang lebih penting lagi, Kak Rey panutanQ buat TOC.
Aku akhirnya ngechat Kak Ammar bulan September untuk dibookingin TOC. Trus aku ajak Vince karena idenya gila-gila dan selera soalnya pasti sama kaya aku.Mulai lah perjalananku ke TOC.
Problemsetter TOC desember:
-satu gak lolos OSK
-satunya lagi gak lolos OSP
Saat Pelatnas
Walaupun saat itu ide soalku ada 3. Aku sudah promosiin ke temen-temen Baliku (Rama dan Tama) "EH INGET TOC DESEMBER YAH!". Pas pelatnas hari pertama, Bu Inge bilang nanti kedepannya bakal ada kegiatan dimana peserta buat soal dan testcase sendiri. Aku mikirnya "Asik, kan tinggal submit soal TOCku doang :v". Terus pas pelatnas kegiatanku untuk ngurus TOC juga minim. Paling ngeproof-ngeproof ide yang masih pending.
Selesai Pelatnas (November)
sekitar 5 hari setelah pelatnas aku liburan ke Jepang, jadi gaada kegiatan apa-apa. Ketika Novermber tiba, aku pikir saatnya fokus TOC, apalagi ada beberapa ide soal lagi yg kupending dulu. Masalahnya, ada tes-tes berantai yaitu TOEFL tanggal 12 November dan SAT tanggal 2 Desember. Aku kontak Vince dia ada ide soal gak, ternyata dia juga fokus sama tesnya dia yaitu ISPO dan SAT. Dan SAT itu susah banget. Jadi kami sepakat untuk fokus itu dulu, nanti Desember baru kita fokus TOC karena gaada kegiatan lagi.
Desember Awal
Yah, ujung-ujungnya Desember juga mulai persiapannya :". TAPI, kalau aku ga ngontak dari September, mungkin taun depan baru dapet ngadain TOC (TOC itu ngantre :v). Akhirnya dibuatkan multichat FB sama kakak-kakak pengurus TOC. Nama grupnya keren lagi "TOC Akhir Tahun" *_*. Ya ideku udh banyak pending sih, aku tinggal ngesolve trus ngeproof aja. Oiya caraku buat soal itu soal dulu baru solusi. Karena aku tuh orangnya ga kreatif :".
Vince juga sering bantu ngeproof soal-soalku. Namun kadang dia suka tiba-tiba ga ON, jadi aku berasa ngomong sendiri di chat :".
Desember Pertengahan (Rejection)
Minggu kedua ada rapat lewat voice chat. Kita gunakan voice chat FB. Nah aku udah ingetin si Vince kemaren berkali-kali jadi sudah aman. Namun di jam yang ditentukan, dia ga nongol :". langsung ku spam LINEnya. Akhirnya mulai aja. Setelah setengah jam, akhirnya Vince muncul dan aku tenang.
Saat rapat ini, aku sudah jadi 4 soal dan Vince jadi 3. Namun ternyata soalku 1 di reject, 1nya lagi soal math terlalu kontroversial, Proofku masih setengah intuitif dan Kakak-kakaknya gamau mengambil resiko, jadi direject dulu :v. Soalnya Vince di ACkan semuanya. Yang mengagumkan, aku kira soal 1D (Sinister Shadow Games) bakal dipermasalahkan, namun saat rapat soal itu dibilang OK dengan relatif cepat :D. Justru soal yang paling bermasalah itu soal "Hari Pertama" dimana kami menghabiskan waktu 30 menit lebih bahas itu. (spoiler dibawah: versi aslinya jauh lebih susah bahkan katanya Vince "Orang PRO aja bisa tertipu").
Salah satu soal yang di reject itu tahun lalu aku submit ke IOI. Yah ternyata disini di reject juga. Katanya itu soal well-known. Padahal tahun lalu aku seneng banget setelah semingguan berhasil ngeproof solusinya :(. Ya aku belajar kalau memang skillku masih cupu.
Jadi sekarang aku punya 2 soal, dan Vince punya 3. Setelah rapat, kami mulai ngerjain descnya. Aku sudah nyimpen ide descku dari lama sih, tinggal masalah implementasi. Kalau Vince gatau, yang jelas suatu hari tiba-tiba descnya Vince di google docs berubah xD.
Aku baru ngerasain sekarang salah satu kerepotan jadi problem setter. Yaitu kalau ngeproof harus beneran di proof. gaada yang namanya "proof by submission". Lumayan lah skillku ngeproof nambah. Awal-awal banyak sekali proofku yang dikoreksi kalau salah dan tidak jarang ditemukan solusi yang lebih general atau bahkan solusi yang jauh berbeda dari sebelumnya.
Minggu Ketiga-Keempat
Aku sudah dapat ide untuk soal baru, yaitu soal Kimia Organik. Sebenernya "problem" ini aku sudah penasaran dari kelas 11 saat belajar bab Hidrokarbon. Gimana kok alkana bentuknya bisa cabang-cabang tapi tetap terjaga rumusnya C_nH_2N+2. Aku juga udah konsul-konsul sama Adik kelasku masalah stabilitas. Kalau bisa-bisa aja ikatannya sembarang asal elektron terpenuhi, namun jarang ditemukan di alam bebas. Awalnya soal ini cuman nentuin apakah ada satu struktur doang atau tidak dan soal ini jadi 2C/1A.
Nah dari 2 soalku yang awal, lagi-lagi 1 bermasalah (NOPE, bukan 1D). Intinya soal itu observasinya keras dan gabisa di solve dalam waktu dua jam apalagi ada soal-soal maut lainnya. Namun aku bilang kalau aku ingin nunjukkin skill buat soalku nanti ke univ jadi disimpen dulu. Lengkap deh aku 3 soal, Vince 3 soal untuk problemset utuh.
BUT WAIT
Akhirnya aku ada Ide untuk pengganti soal tersebut, yaitu soal Akademi Pencyduk (1A). Trus soal Kimia aku ada ide untuk jadiin versi sulitnya, yaitu hitung banyaknya komponen yang mungkin. Lalu aku sadar kalau banyaknya komponen cuman bergantung pada banyaknya edgesnya jadi soal versi sulit dijadikan versi mudah, dan soal versi sulit ditambahkan kesulitannya (gak dijamin graphnya valid) agar algo degreeku kepake :D. Jadi soal mudah dijadikan 2C, sulit 1C.
Sekarang, baru semua soal siap.
BUT WAIT
akhirnya salah satu soalnya Vince (segienam) bermasalah. awalnya soal segienam ini tentang segienam juga, tapi sangat berbeda dengan 2D/1B. Kak Agus menunjukkan kesalahan parah di proof kita dan soalnya pun jadi unsolveable. Sebenernya aku yang bersalah sih karena soal itu kebanyakan aku yang proof :" (Jadi ini salah Vince atau aku sih :v). Beruntungnya, saat mimpi aku mendapatkan ide pengganti soalnya yang juga tentang segienam, Aku bangun jam 2 malam untuk proof yang bener dan Ketemu! Besoknya langsung diskusi sama Vince untuk memperjijik soalnya, dan diterima sama tim TOC! Sekarang soal itu jadi soal 2D/1B.
Aku sudah ekspektasi kalau soal 1D bakal dipermasalahkan cepat atau lambat. Dan benar saja! 3 Hari sebelum TOC akhirnya dipermasalahkan. "Gimana mau analisis graphnya" "Ini lebih cocok dikirim ke IPSC, seriusan" dst. Karena aku menghabiskan waktu 2 minggu untuk ngumpulin kata-kata demi merancang graph yang istimewa, aku melindungi problem ini dengan jiwa-ragaku (ayo coba sebutkan kata yang depannya M, belakangnya V. Atau sebuah kata yang belakangnya J). Akhirnya diambil jalan tengah yaitu coba seorang tester jawab dalam dua jam, kalau dia bisa, maka soal ini diterima. sudah bisa ditebak hasilnya gimana :P.
Nah Mulai minggu keempat, revisi-revisi deskripsi dari kakak-kakak TOC sudah berdatangan. untuk tiap soal sih biasanya ringan-ringan aja, paling masalah koma atau huruf besar. kecuali untuk soal ini:
Akhirnya, semua soal siap... tepat waktu. Untuk buat testcase, harus pake Tcframe. Nah ini gak di support windows dan aku sudah coba berbagai macam virtual box namun entah kenapa gabisa jalan di komputer jadul ini. Beruntung ada Vince yang pake macbook. Aku tentunya juga udah menguasai documentationnya biar bisa ikut buat spec. Semua testcase dibuat oleh Aku dan Vince kecuali Kimia yang dibuat oleh Kak Anthony karena kami masih pemula gatau caranya buat testcase kuat disana :/
(Vince selesai buat spec, aku selesai buat solusi)
Galang: "Bruh, ini solusi gw"
Vince: "tydacccc. bits stdccc"
Aku walaupun tau di mac gabisa pake bits, tapi terkadang lupa ganti karena sudah mendarah daging 2 tahun ngoding :\.
Grand total ide soal yang aku punya selama TOC ini ada 7, dan diterima cuma 3. Banyak juga ya, harusnya bisa pake buat kontes sendiri xD. Ringkasan kenapa gak dipake soal-soal lainku (nama disensor karena masih bisa kukembangkan :P)
Soal 1#: Ternyata well-known
Soal 2#: Gak bisa di proof secara solid
Soal 3#: Observasi mudah, Implementasi muntah (Bersyukurlah 1C gajadi ini :v)
Soal 4#: Yang bahkan belum ku submit dan cuman aku doang yang tau. Ini aku belum ketemu solusinya sampe sekarang xD. (Ingat aku buat soal dulu baru solusi)
Testing H-1
Jadi H-1 ada testing internal yang dibuka untuk semua orang yang terlibat dalam TOC. Dan ada juga "tester misterius" yang saya sendiri gatau siapa. Aku manfaatkan untuk submit-submit berbagai macam solusi untuk cek runtimenya, dan cek deskripsi juga. Hasil testingnya cukup baik. dan akhirnya aku bisa ikut goodbye 2017 dan dapet +19 rating. (apaan sih soal Dnya gak ngerti).
Hari H
Paginya keluargaku berangkat liburan, aku milih gak ikut demi ngurusin TOC ini. Ya, aku ada agenda tersendiri kenapa aku pingin banget ngadain TOC :). Tapi ya efeknya tahun baru aku sendiri lagi :(
Tahun lalu keluargaku ke Hongkong trus aku diam dirumah untuk ambis GCI dan TONAMPTN karena dulu aku ingin menggaet seseorang. sekarang TOC. Tapi, memang itu demi masa depan dan keluargaku juga mendukung.
Trus aku kepikiran apa yang dibilang testernya kemaren, kalau waktunya ga cukup. Aku pingin problemset div1ku dinikmati, jadi yaudah deh akhirnya kami sepakat naikin waktunya jd 2,5 jam. (Div2 bodo amat banyakan soalnya Vince :v)
Kegiatan dari pagi-sore gaada yang berhubungan dengan TOC. Malemnya aku bangun, siap-siap untuk supervisor TOC deh.
1 jam pertama, baru ada 2 AC pada div1. Ternyata soalku susah :". padahal kalau toc aku biasanya kuat sampe soal Div1A-B. Nah ini aku bisa solve soal-soalku semua :\. Sepertinya memang bener kalau soal buatan kita pasti lebih mudah.
1 Jam terakhir. Baru 1 yang AC div2B. trus Div1 A-C udah ada yang ackan berarti setidaknya solveable(?). Agak sedih sih ternyata soalnya lebih susah dari yang kuduga :(
KONTES BERAKHIR.
Kejadian seperti saat buat soal TDC tahun lalu (lomba logika sekolah) terulang lagi, yaitu aku overestimate kemampuanku. Karena biasanya aku mentoknya sampe Div1B, dan aku bisa jawab semua soal-soalku, aku ngira gaada masalah. Ternyata lain. Oke, aku akan jadikan pelajaran untuk kedepannya. (TDC tahun ini sukses soalnya :D).
Scoreboard akhir
Oh iya, Rencana awalnya kan mau ngasi hadiah sticker ke 10 terbaik SMA, dengan rencana kaya peringkat 1-5 dapet 50 coin, peringkat 6-10 dapet 20 coin. namun karena yang AC nonzero SMA cuman 4, yaudah yang itu aja yang dapet hadiahnya. Selamat kepada Fausta, Alghi, Rico, dan Yehezkiel!
Hadiah sticker itu inisiatif aku dan vince, untuk mengundang anak calon OSN untuk mencoba divisi 1 :)
Pembahasan (asumsinya pakai bahasa C++, bahasa lain menyesuaikan). Aku juga kasi rating observasi vs implementasi. Perlu dicatat bahwa rating untuk soal div2 only itu mengasumsikan tingkat kesulitan untuk div2.
===pembahasan dimulai
Hari Pertama (2A)
Observasi: Mudah
Implementasi: Mudah
Pertama kita kalikan dulu A dan Bnya (gunakan long long). Nah apabila kita langsung bagi menggunakan double, pasti digit terakhirnya bakal error karena double hanya akurat sampai 15 digit (termasuk bagian bulatnya) dan long double cuman akurat sampai 20 digit. Kita perhatikan bahwa sebuah bilangan dibagi 9 pasti angka dibelakang komanya itu sisanya yang diulang terus. Jadi kita bisa akali dengan mencetak = (hasil dibagi 9).(ngefor sisa dibagi 9 sebanyak 11 kali)
Tantangan: gimana kalau 1<=A,B<=10^10
Membeli Permen (2A)
Observasi: Mudah
Implementasi: Menengah
Observasinya, yang penting cuman K+P permen terbesar doang. Jadi solusinya, sorting terus buang semua permen kecuali K+P permen terbesar. Kemudian tinggal di permutasikan saja untuk memilih semua kombinasi K permen. Caranya permutasi bisa pake rekursi bab 15 tlx, backtrack, atau next_permutation C++ (solusi juri pake rekursi biasa). Constraint dibuat agar solusi DP juga lolos.
Ini satu-satunya soal yang memenya ompong. *ba dum tss*
Kimia Organik (Mudah) (2C)
Observasi: Sulit
Implementasi: Mudah
Perbedaannya versi mudah dan sulit cuman kalau yang sulit datanya belum tentu valid. Pertama kita asumsikan datanya valid dulu.
Observasi: Suatu C yang mengikat H tidak penting. Karena H hanya bisa mengikat 1, maka pasti H tersebut adalah ujung dan karena data valid, ini tidak perlu dipermasalahkan.
Jadi, kita hanya perlu membuat graph atom C, dengan derajat (banyaknya atom C lain yang terhubung dengannya) itu sesuai dengan inputnya. Untuk memperjelas
C C H H H, mengikat 1 atom C lain, maka derajatnya 1 (Di Kimia disebut atom C Primer)
C C C H H, mengikat 2 atom C lain, derajatnya 2 (Atom C sekunder)
dst.
Jadi, apabila kita bisa membuat graph dengan atom-atom C dengan derajat yang sesuai, maka atom-atom H tinggal ditempel aja dan pasti bisa.
Jadi kita buat dulu array yang berisi derajat setiap atom C. Setelah itu, kita hitung banyaknya edge (ikatan) yang bisa dibuat. Ada lemma berikut:
Lemma: Banyaknya edge pada suatu graph adalah total derajatnya dibagi 2.
Buktinya, misalkan suatu edge menghubungkan A dan B, maka ketika kita menghitung total derajatnya, edge ini dihitung 2x, yaitu di A dan di B. hasil akhirnya tinggal dibagi 2.
Misal banyaknya edgenya ada E, sedangkan total atom C ada V. apabila E>=V-1, maka banyaknya komponen pasti cuma 1. Buktinya pake gambar:
Apabila E<V-1, banyaknya komponen adalah V-E. Idenya, agar semua C terhubung, kan perlu V-1 edge kan. Nah, apabila 1 edge kita ambil, PASTI komponennya TEPAT 1.
Tricky Case:
apabila ada data-data ini muncul, ini sudah pasti 1 komponen dan gak bisa diutak-atik lagi
C H H H H
H C
H C
H C
H C
atau
H H
H H
Yang kedua itu super jahat dan harus di handle secara spesifik di versi susah. Ya aku tau kok gas hidrogen bukan hidrokarbon menurut definisi IUPAC, namun menurut definsi TOC...
Akademi Pencyduk (1A)
Observasi: Menengah
Implementasi: Mudah
Observasi: Di suatu langkah yang optimal, selisih jarak sebelum bergerak dan sesudah bergerak paling banyak 1. (antara sama atau berkurang 1)
jadi, akan optimal apabila penguji dapat bergerak "menjauhi" Vega selama mungkin. Penguji dapat menjauh selama tidak mengenai tembok Apabila penguji sudah kena tembok, dan gak bisa menjauhi jaraknya lagi, maka optimalnya penguji diam saja (biar mudah juga ngitungnya). Maka dari sini didapat observasi kalau Misal penguji awalnya ada di titik (x,y). Observasinya hanya ada 8 petak "optimal" buat penguji, yaitu:
(x,1)
(x,M)
(1,y)
(N,y)
(1,1)
(1,M)
(N,1)
(N,M)
Jadi, untuk setiap titik optimal, kita cek apakah penguji bisa tiba kesana sebelum Vega, apabila bisa, maka jawabannya apabila itu titik terakhir adalah jarak Vega (penguji kesana, diam, lalu tunggu hingga ditangkap Vega). Jarak dua buah titik (x1,y1) (x2,y2) dengan langkah raja (8 arah) adalah max(abs(x2-x1),abs(y2-y1)). Nanti waktu terlama diambil lalu jawabannya ditambah 1 (sesuai spesifikasi soal).
Kenapa ga ini dijadikan 2C? karena kami observasi soal div2 kalau ditambah ini jadi rada simple-simple. aku juga ingin ngenalin graph :).
Tricky Case:
Vega dan penguji pada awalnya berada pada titik yang sama, jawabannya 0 (baca soal lebih teliti)
PR Maut (2D dan 1B)
Observasi: Menengah
Implementasi: Sulit
Awalnya ini solusinya intendednya NlogN per query. Namun akhirnya dimudahkan agar N^3 bisa lolos. Tapi karena solusiku sama Vince pake NlogN, dibawah kita bahas yang itu saja.
Bisa dibagi jadi 2 kasus
N<3 -> jawabannya pasti BISA
N>=3
Apabila solusinya valid, hanya ada 1 segienam yang mungkin dibentuk. Pertama kita cari dulu sisi dari segienam tersebut.
Caranya, kita pilih titik paling pojok kiri dulu (Y terkecil, kalau sama X terkecil). Katakan ini titik pivot. lalu kita sorting titik-titik sisanya berdasarkan sudut yang dibentuk oleh titik tersebut, pivot, dan garis horisontal yang melewati titik pivot. Ini akan membuat titiknya menempati aturan counterclockwise:
Berikut, pada array titik yang baru tersebut, kita hitung jarak dari titik ke-i dan titik ke-(i+1) (siklik, jadi hitung juga jarak titik ke n dengan titik ke 1). ada dua kasus:
-Semua jarak bernilai sama (hanya mungkin pada N=3): artinya titik-titik membentuk segienam sama sisi, jawabannya pasti BISA.
-Ada jarak yang berbeda: sisinya adalah nilai jarak terkecil. ("buktinya" silahkan di trial and error di kertas)
Katakan panjang sisinya s.
dua solusi untuk menjawab:
-Versi Vince: hardcode: (cuman 10 kasus) "Setelah ISPO dimana 1 file bisa 500 baris, 170 baris terasa empuk bagiku". Intinya, mulai dari dua titik bersebelahan, trus hitung jaraknya ke titik selanjutnya berapa. Kalau jarak tertentu, artinya itu titik tertentu. (baca kodenya pasti ngerti, solusi ini 2x lebih cepet dari solusiku lho :P).
-Versi Galang: misal salah satu indeks i adalah salah satu indeks dimana jarak titik ke-i dan ke-(i+1) adalah minimum. Karena hanya mungkin terdapat sebuah segienam, kita bisa generate titik-titik segienamnya dengan indeks i dan i+1 sebagai titik permulaian.
Cara generate: Jadi kita anggap sisi segienamnya sebuah vektor, nah kita perlu cari tau vektor dengan panjang sama, yang terotasi 120 derajat.
Tricky Case:
SI Vince suka banget sama tricky, ada beberapa tricky pada soal ini
-Jarak dua buah titik ga muat long long (tapi masih muat di unsigned long long)
-Tidak ada larangan untuk titik-titik segienam yang tidak masuk input. Jadi titik-titik segienam dapat melebihi 10^9 asal tidak masuk input.
Dan yang paling jahat...
Jadi kesimpulannya, Titik-titiknya dibuat genap agar kordinat segienamnya pasti bulet itu cuman kedok doang >:)
Awalnya constraint soal ini Q=10^6 trus time 1S, namun Vince generate Tcnya sejam ga kelar. Jadi Q=10^5, time=100 ms. kenapa? karena kami tidak mau ada solusi next_permutation makanya kami kira timenya harus ketat. Namun setelah diuji sama tester, timenya yang cocok 2 S xD (solusiku tanpa ios_base aja 700 ms)
Kimia Organtik (Sulit) (1C)
Observasi: Sulit
Implementasi: Mudah
Untuk yang versi sulit, kita perlu selidiki dulu apakah daftar yang dikasi valid. yang perlu di cek:
1. Apakah banyaknya atom H yang diikat atom C sama dengan banyaknya atom C yang diikat atom H
2. Apakah array derajat atom-atom C valid.
Yang pertama mudah di cek, tinggal siapin variabel counter aja.
Untuk yang kedua, kita jadi punya problem baru "diberikan derajat masing-masing titik, apakah bisa dibuat sebuah graph dengan derajat tersebut?". Mungkin apabila kalian coba-coba di kertas, pasti ngerasa kayaknya yang derajatnya paling tinggi itu dipasangin duluan deh, dan memang gitu algorithmanya!. algorithma greedy:
Sort derajatnya secara descengding. Misal Node dengan derajat terbesar itu derajatnya X. Kita buat edge dari node tersebut ke X node dengan derajat paling besar berikutnya. Update arraynya dan sort ulang sampe semua derajat bernilai 0. apabila suatu saat kita tidak dapat melakukan sebuah operasi, maka arraynya ga valid.
Bukti: misalnya pada suatu langkah, kita milih sedang mengoperasikan vertex V. trus di greedy yang dihubungkan sekarang itu vertex A, sedangkan solusi optimal agar terbentuk sebuah graph itu ngehubungin ke vertex B. misalnya derajat(x) menyatakan derajat dari vertex x. Maka perhatikan bahwa derajat(A)>derajat(B). Ada dua kasus, derajat(A) = derajat(B), dan derajat(A)>derajat(B). Kalau kasus pertama sama aja kalau dituker. untuk kasus kedua, tanpa mengurangi generalitas, asumsikan derajat(B)>0, maka derajat(A)>1. Artinya, apabila V dihubungkan ke B, pasti ada vertex lain D yang ngehubungin A. Berarti ada 2 edge, V-B dan D-A. Nah ini kan kalau kita tuker jadi D-B dan V-A ga bakal ngaruh. terbukti.
Apabila kita simulasiin secara langsung bakal O(N^2 log N). Sebuah solusi lain dengan kompleksitas O( N^2) bisa dicapai dengan observasi derajat paling banyak 4, jadi tiap kita update derajat kita bisa "bubble" node yang kita update ke posisi yang benar (O(N) per update) dan karena tiap langkah elemen array berkurang 1, maka jadi algo N^2. Nah algo ini bisa dipercepat jadi NlogN dengan memanfaatkan Heap (Priority_Queue)
Setelah di cek, beres deh balik ke solusi mudah.
Menarik juga, soal versi mudah di 2C, yang sulit di 1C :v
Sinister Shadow Games (Div 1 D)
Observasi: ??? (bingung, pendapat pada beda-beda)
Implementasi: Menengah
Observasi awalnya, ga penting katanya. yang penting cuman huruf depan sama huruf terakhirnya doang.
Ini kan kalau banyaknya kata sedikit, solusi terbaik adalah di solve dengan dp bitmask n*2^n. Namun, karena Nnya 62, maka kita curiga pasti graphnya ada sesuatu.
Trus graphnya bisa di kompres jadi 26 nodes untuk tiap alfabet. Jadi apabila ada kata dengan awalan i dan akhiran j. buat UNDIRECTED edge i-j. berikutnya, kita observasi bahwa apabila ada suatu node di graph yang tersebut yang apabila dihapus akan memisahkan graph, maka itu adalah titik pemisah (ini disebut articulation point dalam CS). Maka kita cari semua titik yang mungkin, algoritma yang bisa dilakukan adalah cukup coba hapus hurufnya satu-satu, trus cek masih nyambung gak graphnya. kalau articulation pointnya udah ketemu semua, semuanya kita hapus dan jalanin DFS untuk ketemu grup-grup katanya. Ilustrasi (ini graphnya sudah ku kelompokkan demi memperjelas).
Jadi, kita hanya perlu dp bitmask untuk suatu kelompok tertentu, dan apabila pindah kelompok kita bisa reset dp bitmasknya! pengelompokkan bisa dilakukan setiap operasi dua dan solusi ini (dengan menggunapan map untuk menyimpan DP) akan AC karena ke sparsean graphnya.
Ada observasi yang lebih mempermudah lagi: kita perhatikan bahwa kata-kata cadangan tidak akan mengubah kelompok-kelompok tersebut (caranya perhatikan ya di print aja huruf tiap kelompok trus bandingin sama kata cadangan). Jadi komputasi diatas cukup dilakukan di awal. Selanjutnya dapat diperhatikan mau bagaimanapun ditukar-tukar kelompoknya, banyaknya huruf pada suatu kelompok paling banyak 20. jadi solusi N*2^20 dapat dilakukan dan inilah solusi juri.
BONUS: Ada gak solusi yang gak perlu bongkar graphnya, memory cuma 2 MB, timenya 10x lebih cepet dari solusi diatas?
Sebenernya, memang graph yang aku buat ini rada istimewa. dengan edge sparse, degree maksimal 5, dll, Bruteforce 2^62 aja cuma 1500 ms. jadi sebenernya solusi apapun yang lebih cepet dari 2^62 bakal AC. Untuk merancang graph seperti ini dua minggu loh ngumpulin katanya :(.
Soal ini terinspirasi dari dua soal:
-Nowruz (IOI 2017). Selesai IOI, tim Korea ngamuk karena mereka mikirin solusi untuk general graph padahal testcasenya sparse graph semua. Sama seperti soal ini, Kalau aku kasi 62 kata yang berawalan dan berakhiran E bakal mampus tentunya. Namun disini perhatikan setiap huruf munculnya 2-3 kali dan pasangan kata dengan awalan dan akhiran sama itu sedikit. Bahkan solusi bruteforce 2^62 pun cuma 1500 ms.
-Soal ini: http://ceoi.inf.elte.hu/probarch/15/day2/day2task3-eng.pdf
ini solusi resminya.
==pembahasan selesai
Ini deh paket lengkap solusi TOC kali ini, bisa di submit di TLX biar nambah rangkingnya. https://drive.google.com/drive/folders/1N9TA_Y3xVybiX4ul-vZnhr4K0v6rWBwe?usp=sharing
funfact: untuk div 1, semua soal memiliki tricky case super jahat, kecuali soal D (kalau itumah soal udah jahat).
Nah sekarang aku akan membahas unsur instrinstik soal-soalku.
Pertama kalau belum sadar,
Vega = VincE GAlang
non-Vega =nama flora.
Jadi aku propose 3 soal, Kimia Organik, Akademi Pencyduk, dan Sinister Shadow Games. Soal ini descnya kubuat sangat spesific dan menangkap berbagai hal tentang diriku.
Akademi Pencyduk: Disini aku ngomongin budaya meme di Indonesia, Dan keindetikanku sebagai tukang ciduk di ekstra komputer. aku seneng banget sama meme-meme tipe tulisan dan aku ngoleksi di HP. Kalau masalah ciduk itu sih soalnya dulu pas kelas 11, kalau ada kumpul ekstra pulang sekolah trus ada yg ijin pulkam, aku cek mekdi deket sekolah ada dia gak. Tidak jarang terciduk.
Kimia Organik: Bagian pertama ngomongin passion lainku selain informatika, yaitu Kimia. Gimana aku coba nyusun desc dimana yang yang ngerti kimia dikit bakal seneng dan tetep dapat dimengerti orang yang non komputer. Sedangkan bagian ketua melukiskan perjalanan asmaraku (tidak ada hubungannya sama kimia).
Sinister Shadow Games: Kalau yang ini sih gabungan dari 3 hobi favoritku: Anime, Sherlock Holmes, dan Yu-Gi-Oh!
Anime = 2 Kakak-Adik jago Game? Sambung Kata? Jebret?
Sherlock = Aku seneng banget sama novelnya, dirumah udah ada semua serialnya. keren banget deh pokoknya dan recomended :). Nah kan ada filmnya yang kedua "A Game of Shadows" yang konotasinya ada sebuah game maut padahal yang dimainin catur. Nah disini juga serupa risknya, Suatu "Game maut" yang ternyata cuma sambung kata. Oiya, sebelumnya nama soal ini maunya "A Game of Shadows"
Yu-Gi-Oh! = Di desc soal ini, hanya berfungsi sebagai "bumbu" doang. Game kartu Yu-Gi-Oh! itu masa SMPku :). Walaupun udah gak dikasi main lagi karena dikira judi, aku tetep ikutin kok meta terupdatenya di youtube sampe sekarang (spyral, pendulum magician, dkk).
Urutan kemunculan refrencenya juga ngaruh. Yu-Gi-Oh! muncul duluan karena aku paling pertama terekspos ke itu, trus anime, trus baru Sheclock Holmes. "Porsinya" juga ngaruh. Di soalnya paling banyak ngomongin tentang porsi animenya, karena aku sampe sekarang masih nonton anime, trus Ada sedikit bumbu Yu-Gi-Oh! di bagian atas deskripsi karena masih ngikutin di youtube, trus ada Sherlock Holmes refrence dikit (yang mungkin orang ga nyadar kalau ga kukasi tau) karena aku udah selesai baca semua bukunya taun lalu dan ga baca lagi karena masih ingat dengan jelas. Ada beberapa easter egg lagi sih, seperti kenapa namanya Mawar. Tapi itu dibiarkan inside jokes saja.
sekian unsur intristiknya. Semoga setelah baca, problemku menjadi lebih menarik :). Maaf apabila ada soal yang kurang berkenan seperti PR Maut (Marahin Vince) atau Sinister Shadow Games, atau kalau soalnya "alay". Itu semua sudah direncanakan sesuai dengan tema TOCnya yaitu Kidz Jaman Now.
aku akhiri dengan quotes ini kali:
Midoriya: "Those weren't just random problems either, They're targeted, and every single one of them, is more than a hundred percent of his power"
Aku akhirnya ngechat Kak Ammar bulan September untuk dibookingin TOC. Trus aku ajak Vince karena idenya gila-gila dan selera soalnya pasti sama kaya aku.Mulai lah perjalananku ke TOC.
Problemsetter TOC desember:
-satu gak lolos OSK
-satunya lagi gak lolos OSP
Saat Pelatnas
Walaupun saat itu ide soalku ada 3. Aku sudah promosiin ke temen-temen Baliku (Rama dan Tama) "EH INGET TOC DESEMBER YAH!". Pas pelatnas hari pertama, Bu Inge bilang nanti kedepannya bakal ada kegiatan dimana peserta buat soal dan testcase sendiri. Aku mikirnya "Asik, kan tinggal submit soal TOCku doang :v". Terus pas pelatnas kegiatanku untuk ngurus TOC juga minim. Paling ngeproof-ngeproof ide yang masih pending.
Selesai Pelatnas (November)
sekitar 5 hari setelah pelatnas aku liburan ke Jepang, jadi gaada kegiatan apa-apa. Ketika Novermber tiba, aku pikir saatnya fokus TOC, apalagi ada beberapa ide soal lagi yg kupending dulu. Masalahnya, ada tes-tes berantai yaitu TOEFL tanggal 12 November dan SAT tanggal 2 Desember. Aku kontak Vince dia ada ide soal gak, ternyata dia juga fokus sama tesnya dia yaitu ISPO dan SAT. Dan SAT itu susah banget. Jadi kami sepakat untuk fokus itu dulu, nanti Desember baru kita fokus TOC karena gaada kegiatan lagi.
Desember Awal
Yah, ujung-ujungnya Desember juga mulai persiapannya :". TAPI, kalau aku ga ngontak dari September, mungkin taun depan baru dapet ngadain TOC (TOC itu ngantre :v). Akhirnya dibuatkan multichat FB sama kakak-kakak pengurus TOC. Nama grupnya keren lagi "TOC Akhir Tahun" *_*. Ya ideku udh banyak pending sih, aku tinggal ngesolve trus ngeproof aja. Oiya caraku buat soal itu soal dulu baru solusi. Karena aku tuh orangnya ga kreatif :".
Vince juga sering bantu ngeproof soal-soalku. Namun kadang dia suka tiba-tiba ga ON, jadi aku berasa ngomong sendiri di chat :".
Desember Pertengahan (Rejection)
Minggu kedua ada rapat lewat voice chat. Kita gunakan voice chat FB. Nah aku udah ingetin si Vince kemaren berkali-kali jadi sudah aman. Namun di jam yang ditentukan, dia ga nongol :". langsung ku spam LINEnya. Akhirnya mulai aja. Setelah setengah jam, akhirnya Vince muncul dan aku tenang.
Saat rapat ini, aku sudah jadi 4 soal dan Vince jadi 3. Namun ternyata soalku 1 di reject, 1nya lagi soal math terlalu kontroversial, Proofku masih setengah intuitif dan Kakak-kakaknya gamau mengambil resiko, jadi direject dulu :v. Soalnya Vince di ACkan semuanya. Yang mengagumkan, aku kira soal 1D (Sinister Shadow Games) bakal dipermasalahkan, namun saat rapat soal itu dibilang OK dengan relatif cepat :D. Justru soal yang paling bermasalah itu soal "Hari Pertama" dimana kami menghabiskan waktu 30 menit lebih bahas itu. (spoiler dibawah: versi aslinya jauh lebih susah bahkan katanya Vince "Orang PRO aja bisa tertipu").
Salah satu soal yang di reject itu tahun lalu aku submit ke IOI. Yah ternyata disini di reject juga. Katanya itu soal well-known. Padahal tahun lalu aku seneng banget setelah semingguan berhasil ngeproof solusinya :(. Ya aku belajar kalau memang skillku masih cupu.
Jadi sekarang aku punya 2 soal, dan Vince punya 3. Setelah rapat, kami mulai ngerjain descnya. Aku sudah nyimpen ide descku dari lama sih, tinggal masalah implementasi. Kalau Vince gatau, yang jelas suatu hari tiba-tiba descnya Vince di google docs berubah xD.
Aku baru ngerasain sekarang salah satu kerepotan jadi problem setter. Yaitu kalau ngeproof harus beneran di proof. gaada yang namanya "proof by submission". Lumayan lah skillku ngeproof nambah. Awal-awal banyak sekali proofku yang dikoreksi kalau salah dan tidak jarang ditemukan solusi yang lebih general atau bahkan solusi yang jauh berbeda dari sebelumnya.
Minggu Ketiga-Keempat
Aku sudah dapat ide untuk soal baru, yaitu soal Kimia Organik. Sebenernya "problem" ini aku sudah penasaran dari kelas 11 saat belajar bab Hidrokarbon. Gimana kok alkana bentuknya bisa cabang-cabang tapi tetap terjaga rumusnya C_nH_2N+2. Aku juga udah konsul-konsul sama Adik kelasku masalah stabilitas. Kalau bisa-bisa aja ikatannya sembarang asal elektron terpenuhi, namun jarang ditemukan di alam bebas. Awalnya soal ini cuman nentuin apakah ada satu struktur doang atau tidak dan soal ini jadi 2C/1A.
Nah dari 2 soalku yang awal, lagi-lagi 1 bermasalah (NOPE, bukan 1D). Intinya soal itu observasinya keras dan gabisa di solve dalam waktu dua jam apalagi ada soal-soal maut lainnya. Namun aku bilang kalau aku ingin nunjukkin skill buat soalku nanti ke univ jadi disimpen dulu. Lengkap deh aku 3 soal, Vince 3 soal untuk problemset utuh.
BUT WAIT
Akhirnya aku ada Ide untuk pengganti soal tersebut, yaitu soal Akademi Pencyduk (1A). Trus soal Kimia aku ada ide untuk jadiin versi sulitnya, yaitu hitung banyaknya komponen yang mungkin. Lalu aku sadar kalau banyaknya komponen cuman bergantung pada banyaknya edgesnya jadi soal versi sulit dijadikan versi mudah, dan soal versi sulit ditambahkan kesulitannya (gak dijamin graphnya valid) agar algo degreeku kepake :D. Jadi soal mudah dijadikan 2C, sulit 1C.
Sekarang, baru semua soal siap.
BUT WAIT
akhirnya salah satu soalnya Vince (segienam) bermasalah. awalnya soal segienam ini tentang segienam juga, tapi sangat berbeda dengan 2D/1B. Kak Agus menunjukkan kesalahan parah di proof kita dan soalnya pun jadi unsolveable. Sebenernya aku yang bersalah sih karena soal itu kebanyakan aku yang proof :" (Jadi ini salah Vince atau aku sih :v). Beruntungnya, saat mimpi aku mendapatkan ide pengganti soalnya yang juga tentang segienam, Aku bangun jam 2 malam untuk proof yang bener dan Ketemu! Besoknya langsung diskusi sama Vince untuk memperjijik soalnya, dan diterima sama tim TOC! Sekarang soal itu jadi soal 2D/1B.
Aku sudah ekspektasi kalau soal 1D bakal dipermasalahkan cepat atau lambat. Dan benar saja! 3 Hari sebelum TOC akhirnya dipermasalahkan. "Gimana mau analisis graphnya" "Ini lebih cocok dikirim ke IPSC, seriusan" dst. Karena aku menghabiskan waktu 2 minggu untuk ngumpulin kata-kata demi merancang graph yang istimewa, aku melindungi problem ini dengan jiwa-ragaku (ayo coba sebutkan kata yang depannya M, belakangnya V. Atau sebuah kata yang belakangnya J). Akhirnya diambil jalan tengah yaitu coba seorang tester jawab dalam dua jam, kalau dia bisa, maka soal ini diterima. sudah bisa ditebak hasilnya gimana :P.
Nah Mulai minggu keempat, revisi-revisi deskripsi dari kakak-kakak TOC sudah berdatangan. untuk tiap soal sih biasanya ringan-ringan aja, paling masalah koma atau huruf besar. kecuali untuk soal ini:
 |
| My eyesss.... (total 100+ perbaikan) |
Akhirnya, semua soal siap... tepat waktu. Untuk buat testcase, harus pake Tcframe. Nah ini gak di support windows dan aku sudah coba berbagai macam virtual box namun entah kenapa gabisa jalan di komputer jadul ini. Beruntung ada Vince yang pake macbook. Aku tentunya juga udah menguasai documentationnya biar bisa ikut buat spec. Semua testcase dibuat oleh Aku dan Vince kecuali Kimia yang dibuat oleh Kak Anthony karena kami masih pemula gatau caranya buat testcase kuat disana :/
(Vince selesai buat spec, aku selesai buat solusi)
Galang: "Bruh, ini solusi gw"
Vince: "tydacccc. bits stdccc"
Aku walaupun tau di mac gabisa pake bits, tapi terkadang lupa ganti karena sudah mendarah daging 2 tahun ngoding :\.
Grand total ide soal yang aku punya selama TOC ini ada 7, dan diterima cuma 3. Banyak juga ya, harusnya bisa pake buat kontes sendiri xD. Ringkasan kenapa gak dipake soal-soal lainku (nama disensor karena masih bisa kukembangkan :P)
Soal 1#: Ternyata well-known
Soal 2#: Gak bisa di proof secara solid
Soal 3#: Observasi mudah, Implementasi muntah (Bersyukurlah 1C gajadi ini :v)
Soal 4#: Yang bahkan belum ku submit dan cuman aku doang yang tau. Ini aku belum ketemu solusinya sampe sekarang xD. (Ingat aku buat soal dulu baru solusi)
Testing H-1
Jadi H-1 ada testing internal yang dibuka untuk semua orang yang terlibat dalam TOC. Dan ada juga "tester misterius" yang saya sendiri gatau siapa. Aku manfaatkan untuk submit-submit berbagai macam solusi untuk cek runtimenya, dan cek deskripsi juga. Hasil testingnya cukup baik. dan akhirnya aku bisa ikut goodbye 2017 dan dapet +19 rating. (apaan sih soal Dnya gak ngerti).
 |
| Supervisor? not bad |
Hari H
Paginya keluargaku berangkat liburan, aku milih gak ikut demi ngurusin TOC ini. Ya, aku ada agenda tersendiri kenapa aku pingin banget ngadain TOC :). Tapi ya efeknya tahun baru aku sendiri lagi :(
Tahun lalu keluargaku ke Hongkong trus aku diam dirumah untuk ambis GCI dan TONAMPTN karena dulu aku ingin menggaet seseorang. sekarang TOC. Tapi, memang itu demi masa depan dan keluargaku juga mendukung.
Trus aku kepikiran apa yang dibilang testernya kemaren, kalau waktunya ga cukup. Aku pingin problemset div1ku dinikmati, jadi yaudah deh akhirnya kami sepakat naikin waktunya jd 2,5 jam. (Div2 bodo amat banyakan soalnya Vince :v)
Kegiatan dari pagi-sore gaada yang berhubungan dengan TOC. Malemnya aku bangun, siap-siap untuk supervisor TOC deh.
1 jam pertama, baru ada 2 AC pada div1. Ternyata soalku susah :". padahal kalau toc aku biasanya kuat sampe soal Div1A-B. Nah ini aku bisa solve soal-soalku semua :\. Sepertinya memang bener kalau soal buatan kita pasti lebih mudah.
1 Jam terakhir. Baru 1 yang AC div2B. trus Div1 A-C udah ada yang ackan berarti setidaknya solveable(?). Agak sedih sih ternyata soalnya lebih susah dari yang kuduga :(
 |
| Bisa regrade submission, feels like admin |
KONTES BERAKHIR.
Kejadian seperti saat buat soal TDC tahun lalu (lomba logika sekolah) terulang lagi, yaitu aku overestimate kemampuanku. Karena biasanya aku mentoknya sampe Div1B, dan aku bisa jawab semua soal-soalku, aku ngira gaada masalah. Ternyata lain. Oke, aku akan jadikan pelajaran untuk kedepannya. (TDC tahun ini sukses soalnya :D).
Scoreboard akhir
Scoreboard akhir divisi 1
 |
| Scoreboard akhir divisi 2 |
Hadiah sticker itu inisiatif aku dan vince, untuk mengundang anak calon OSN untuk mencoba divisi 1 :)
 |
| no comment |
Pembahasan (asumsinya pakai bahasa C++, bahasa lain menyesuaikan). Aku juga kasi rating observasi vs implementasi. Perlu dicatat bahwa rating untuk soal div2 only itu mengasumsikan tingkat kesulitan untuk div2.
===pembahasan dimulai
Hari Pertama (2A)
Observasi: Mudah
Implementasi: Mudah
Pertama kita kalikan dulu A dan Bnya (gunakan long long). Nah apabila kita langsung bagi menggunakan double, pasti digit terakhirnya bakal error karena double hanya akurat sampai 15 digit (termasuk bagian bulatnya) dan long double cuman akurat sampai 20 digit. Kita perhatikan bahwa sebuah bilangan dibagi 9 pasti angka dibelakang komanya itu sisanya yang diulang terus. Jadi kita bisa akali dengan mencetak = (hasil dibagi 9).(ngefor sisa dibagi 9 sebanyak 11 kali)
Tantangan: gimana kalau 1<=A,B<=10^10
Membeli Permen (2A)
Observasi: Mudah
Implementasi: Menengah
Observasinya, yang penting cuman K+P permen terbesar doang. Jadi solusinya, sorting terus buang semua permen kecuali K+P permen terbesar. Kemudian tinggal di permutasikan saja untuk memilih semua kombinasi K permen. Caranya permutasi bisa pake rekursi bab 15 tlx, backtrack, atau next_permutation C++ (solusi juri pake rekursi biasa). Constraint dibuat agar solusi DP juga lolos.
Ini satu-satunya soal yang memenya ompong. *ba dum tss*
Kimia Organik (Mudah) (2C)
Observasi: Sulit
Implementasi: Mudah
Perbedaannya versi mudah dan sulit cuman kalau yang sulit datanya belum tentu valid. Pertama kita asumsikan datanya valid dulu.
Observasi: Suatu C yang mengikat H tidak penting. Karena H hanya bisa mengikat 1, maka pasti H tersebut adalah ujung dan karena data valid, ini tidak perlu dipermasalahkan.
Jadi, kita hanya perlu membuat graph atom C, dengan derajat (banyaknya atom C lain yang terhubung dengannya) itu sesuai dengan inputnya. Untuk memperjelas
C C H H H, mengikat 1 atom C lain, maka derajatnya 1 (Di Kimia disebut atom C Primer)
C C C H H, mengikat 2 atom C lain, derajatnya 2 (Atom C sekunder)
dst.
Jadi, apabila kita bisa membuat graph dengan atom-atom C dengan derajat yang sesuai, maka atom-atom H tinggal ditempel aja dan pasti bisa.
Jadi kita buat dulu array yang berisi derajat setiap atom C. Setelah itu, kita hitung banyaknya edge (ikatan) yang bisa dibuat. Ada lemma berikut:
Lemma: Banyaknya edge pada suatu graph adalah total derajatnya dibagi 2.
Buktinya, misalkan suatu edge menghubungkan A dan B, maka ketika kita menghitung total derajatnya, edge ini dihitung 2x, yaitu di A dan di B. hasil akhirnya tinggal dibagi 2.
Misal banyaknya edgenya ada E, sedangkan total atom C ada V. apabila E>=V-1, maka banyaknya komponen pasti cuma 1. Buktinya pake gambar:
 |
| Dari sini, tidak susah mengeneralisasi kalau ada edge lebih di suatu komponen, edge tersebut pasti bisa dipake untuk nyambungin komponen lain tanpa merubah apa-apa tentang derajatnya |
Apabila E<V-1, banyaknya komponen adalah V-E. Idenya, agar semua C terhubung, kan perlu V-1 edge kan. Nah, apabila 1 edge kita ambil, PASTI komponennya TEPAT 1.
Tricky Case:
apabila ada data-data ini muncul, ini sudah pasti 1 komponen dan gak bisa diutak-atik lagi
C H H H H
H C
H C
H C
H C
atau
H H
H H
Yang kedua itu super jahat dan harus di handle secara spesifik di versi susah. Ya aku tau kok gas hidrogen bukan hidrokarbon menurut definisi IUPAC, namun menurut definsi TOC...
Akademi Pencyduk (1A)
Observasi: Menengah
Implementasi: Mudah
Observasi: Di suatu langkah yang optimal, selisih jarak sebelum bergerak dan sesudah bergerak paling banyak 1. (antara sama atau berkurang 1)
jadi, akan optimal apabila penguji dapat bergerak "menjauhi" Vega selama mungkin. Penguji dapat menjauh selama tidak mengenai tembok Apabila penguji sudah kena tembok, dan gak bisa menjauhi jaraknya lagi, maka optimalnya penguji diam saja (biar mudah juga ngitungnya). Maka dari sini didapat observasi kalau Misal penguji awalnya ada di titik (x,y). Observasinya hanya ada 8 petak "optimal" buat penguji, yaitu:
(x,1)
(x,M)
(1,y)
(N,y)
(1,1)
(1,M)
(N,1)
(N,M)
Jadi, untuk setiap titik optimal, kita cek apakah penguji bisa tiba kesana sebelum Vega, apabila bisa, maka jawabannya apabila itu titik terakhir adalah jarak Vega (penguji kesana, diam, lalu tunggu hingga ditangkap Vega). Jarak dua buah titik (x1,y1) (x2,y2) dengan langkah raja (8 arah) adalah max(abs(x2-x1),abs(y2-y1)). Nanti waktu terlama diambil lalu jawabannya ditambah 1 (sesuai spesifikasi soal).
Kenapa ga ini dijadikan 2C? karena kami observasi soal div2 kalau ditambah ini jadi rada simple-simple. aku juga ingin ngenalin graph :).
Tricky Case:
Vega dan penguji pada awalnya berada pada titik yang sama, jawabannya 0 (baca soal lebih teliti)
PR Maut (2D dan 1B)
Observasi: Menengah
Implementasi: Sulit
Awalnya ini solusinya intendednya NlogN per query. Namun akhirnya dimudahkan agar N^3 bisa lolos. Tapi karena solusiku sama Vince pake NlogN, dibawah kita bahas yang itu saja.
Bisa dibagi jadi 2 kasus
N<3 -> jawabannya pasti BISA
N>=3
Apabila solusinya valid, hanya ada 1 segienam yang mungkin dibentuk. Pertama kita cari dulu sisi dari segienam tersebut.
Caranya, kita pilih titik paling pojok kiri dulu (Y terkecil, kalau sama X terkecil). Katakan ini titik pivot. lalu kita sorting titik-titik sisanya berdasarkan sudut yang dibentuk oleh titik tersebut, pivot, dan garis horisontal yang melewati titik pivot. Ini akan membuat titiknya menempati aturan counterclockwise:
Berikut, pada array titik yang baru tersebut, kita hitung jarak dari titik ke-i dan titik ke-(i+1) (siklik, jadi hitung juga jarak titik ke n dengan titik ke 1). ada dua kasus:
-Semua jarak bernilai sama (hanya mungkin pada N=3): artinya titik-titik membentuk segienam sama sisi, jawabannya pasti BISA.
-Ada jarak yang berbeda: sisinya adalah nilai jarak terkecil. ("buktinya" silahkan di trial and error di kertas)
Katakan panjang sisinya s.
dua solusi untuk menjawab:
-Versi Vince: hardcode: (cuman 10 kasus) "Setelah ISPO dimana 1 file bisa 500 baris, 170 baris terasa empuk bagiku". Intinya, mulai dari dua titik bersebelahan, trus hitung jaraknya ke titik selanjutnya berapa. Kalau jarak tertentu, artinya itu titik tertentu. (baca kodenya pasti ngerti, solusi ini 2x lebih cepet dari solusiku lho :P).
-Versi Galang: misal salah satu indeks i adalah salah satu indeks dimana jarak titik ke-i dan ke-(i+1) adalah minimum. Karena hanya mungkin terdapat sebuah segienam, kita bisa generate titik-titik segienamnya dengan indeks i dan i+1 sebagai titik permulaian.
Cara generate: Jadi kita anggap sisi segienamnya sebuah vektor, nah kita perlu cari tau vektor dengan panjang sama, yang terotasi 120 derajat.
 |
| a,b = konstanta x dan y dicari |
 |
| sisanya diserahkan sebagai latihan (kehabisan tempat) lagi dikit banget kok... |
Tricky Case:
SI Vince suka banget sama tricky, ada beberapa tricky pada soal ini
-Jarak dua buah titik ga muat long long (tapi masih muat di unsigned long long)
-Tidak ada larangan untuk titik-titik segienam yang tidak masuk input. Jadi titik-titik segienam dapat melebihi 10^9 asal tidak masuk input.
Dan yang paling jahat...
Jadi kesimpulannya, Titik-titiknya dibuat genap agar kordinat segienamnya pasti bulet itu cuman kedok doang >:)
Awalnya constraint soal ini Q=10^6 trus time 1S, namun Vince generate Tcnya sejam ga kelar. Jadi Q=10^5, time=100 ms. kenapa? karena kami tidak mau ada solusi next_permutation makanya kami kira timenya harus ketat. Namun setelah diuji sama tester, timenya yang cocok 2 S xD (solusiku tanpa ios_base aja 700 ms)
Kimia Organtik (Sulit) (1C)
Observasi: Sulit
Implementasi: Mudah
Untuk yang versi sulit, kita perlu selidiki dulu apakah daftar yang dikasi valid. yang perlu di cek:
1. Apakah banyaknya atom H yang diikat atom C sama dengan banyaknya atom C yang diikat atom H
2. Apakah array derajat atom-atom C valid.
Yang pertama mudah di cek, tinggal siapin variabel counter aja.
Untuk yang kedua, kita jadi punya problem baru "diberikan derajat masing-masing titik, apakah bisa dibuat sebuah graph dengan derajat tersebut?". Mungkin apabila kalian coba-coba di kertas, pasti ngerasa kayaknya yang derajatnya paling tinggi itu dipasangin duluan deh, dan memang gitu algorithmanya!. algorithma greedy:
Sort derajatnya secara descengding. Misal Node dengan derajat terbesar itu derajatnya X. Kita buat edge dari node tersebut ke X node dengan derajat paling besar berikutnya. Update arraynya dan sort ulang sampe semua derajat bernilai 0. apabila suatu saat kita tidak dapat melakukan sebuah operasi, maka arraynya ga valid.
Bukti: misalnya pada suatu langkah, kita milih sedang mengoperasikan vertex V. trus di greedy yang dihubungkan sekarang itu vertex A, sedangkan solusi optimal agar terbentuk sebuah graph itu ngehubungin ke vertex B. misalnya derajat(x) menyatakan derajat dari vertex x. Maka perhatikan bahwa derajat(A)>derajat(B). Ada dua kasus, derajat(A) = derajat(B), dan derajat(A)>derajat(B). Kalau kasus pertama sama aja kalau dituker. untuk kasus kedua, tanpa mengurangi generalitas, asumsikan derajat(B)>0, maka derajat(A)>1. Artinya, apabila V dihubungkan ke B, pasti ada vertex lain D yang ngehubungin A. Berarti ada 2 edge, V-B dan D-A. Nah ini kan kalau kita tuker jadi D-B dan V-A ga bakal ngaruh. terbukti.
Apabila kita simulasiin secara langsung bakal O(N^2 log N). Sebuah solusi lain dengan kompleksitas O( N^2) bisa dicapai dengan observasi derajat paling banyak 4, jadi tiap kita update derajat kita bisa "bubble" node yang kita update ke posisi yang benar (O(N) per update) dan karena tiap langkah elemen array berkurang 1, maka jadi algo N^2. Nah algo ini bisa dipercepat jadi NlogN dengan memanfaatkan Heap (Priority_Queue)
Setelah di cek, beres deh balik ke solusi mudah.
Sinister Shadow Games (Div 1 D)
Observasi: ??? (bingung, pendapat pada beda-beda)
Implementasi: Menengah
Observasi awalnya, ga penting katanya. yang penting cuman huruf depan sama huruf terakhirnya doang.
Ini kan kalau banyaknya kata sedikit, solusi terbaik adalah di solve dengan dp bitmask n*2^n. Namun, karena Nnya 62, maka kita curiga pasti graphnya ada sesuatu.
Trus graphnya bisa di kompres jadi 26 nodes untuk tiap alfabet. Jadi apabila ada kata dengan awalan i dan akhiran j. buat UNDIRECTED edge i-j. berikutnya, kita observasi bahwa apabila ada suatu node di graph yang tersebut yang apabila dihapus akan memisahkan graph, maka itu adalah titik pemisah (ini disebut articulation point dalam CS). Maka kita cari semua titik yang mungkin, algoritma yang bisa dilakukan adalah cukup coba hapus hurufnya satu-satu, trus cek masih nyambung gak graphnya. kalau articulation pointnya udah ketemu semua, semuanya kita hapus dan jalanin DFS untuk ketemu grup-grup katanya. Ilustrasi (ini graphnya sudah ku kelompokkan demi memperjelas).
 |
| vertex = 1 huruf |
Jadi, kita hanya perlu dp bitmask untuk suatu kelompok tertentu, dan apabila pindah kelompok kita bisa reset dp bitmasknya! pengelompokkan bisa dilakukan setiap operasi dua dan solusi ini (dengan menggunapan map untuk menyimpan DP) akan AC karena ke sparsean graphnya.
Ada observasi yang lebih mempermudah lagi: kita perhatikan bahwa kata-kata cadangan tidak akan mengubah kelompok-kelompok tersebut (caranya perhatikan ya di print aja huruf tiap kelompok trus bandingin sama kata cadangan). Jadi komputasi diatas cukup dilakukan di awal. Selanjutnya dapat diperhatikan mau bagaimanapun ditukar-tukar kelompoknya, banyaknya huruf pada suatu kelompok paling banyak 20. jadi solusi N*2^20 dapat dilakukan dan inilah solusi juri.
BONUS: Ada gak solusi yang gak perlu bongkar graphnya, memory cuma 2 MB, timenya 10x lebih cepet dari solusi diatas?
Sebenernya, memang graph yang aku buat ini rada istimewa. dengan edge sparse, degree maksimal 5, dll, Bruteforce 2^62 aja cuma 1500 ms. jadi sebenernya solusi apapun yang lebih cepet dari 2^62 bakal AC. Untuk merancang graph seperti ini dua minggu loh ngumpulin katanya :(.
Soal ini terinspirasi dari dua soal:
-Nowruz (IOI 2017). Selesai IOI, tim Korea ngamuk karena mereka mikirin solusi untuk general graph padahal testcasenya sparse graph semua. Sama seperti soal ini, Kalau aku kasi 62 kata yang berawalan dan berakhiran E bakal mampus tentunya. Namun disini perhatikan setiap huruf munculnya 2-3 kali dan pasangan kata dengan awalan dan akhiran sama itu sedikit. Bahkan solusi bruteforce 2^62 pun cuma 1500 ms.
-Soal ini: http://ceoi.inf.elte.hu/probarch/15/day2/day2task3-eng.pdf
ini solusi resminya.
 |
| buset dah graphnya |
==pembahasan selesai
Ini deh paket lengkap solusi TOC kali ini, bisa di submit di TLX biar nambah rangkingnya. https://drive.google.com/drive/folders/1N9TA_Y3xVybiX4ul-vZnhr4K0v6rWBwe?usp=sharing
funfact: untuk div 1, semua soal memiliki tricky case super jahat, kecuali soal D (kalau itumah soal udah jahat).
Nah sekarang aku akan membahas unsur instrinstik soal-soalku.
Pertama kalau belum sadar,
Vega = VincE GAlang
non-Vega =nama flora.
Jadi aku propose 3 soal, Kimia Organik, Akademi Pencyduk, dan Sinister Shadow Games. Soal ini descnya kubuat sangat spesific dan menangkap berbagai hal tentang diriku.
Akademi Pencyduk: Disini aku ngomongin budaya meme di Indonesia, Dan keindetikanku sebagai tukang ciduk di ekstra komputer. aku seneng banget sama meme-meme tipe tulisan dan aku ngoleksi di HP. Kalau masalah ciduk itu sih soalnya dulu pas kelas 11, kalau ada kumpul ekstra pulang sekolah trus ada yg ijin pulkam, aku cek mekdi deket sekolah ada dia gak. Tidak jarang terciduk.
Kimia Organik: Bagian pertama ngomongin passion lainku selain informatika, yaitu Kimia. Gimana aku coba nyusun desc dimana yang yang ngerti kimia dikit bakal seneng dan tetep dapat dimengerti orang yang non komputer. Sedangkan bagian ketua melukiskan perjalanan asmaraku (tidak ada hubungannya sama kimia).
Sinister Shadow Games: Kalau yang ini sih gabungan dari 3 hobi favoritku: Anime, Sherlock Holmes, dan Yu-Gi-Oh!
Anime = 2 Kakak-Adik jago Game? Sambung Kata? Jebret?
Sherlock = Aku seneng banget sama novelnya, dirumah udah ada semua serialnya. keren banget deh pokoknya dan recomended :). Nah kan ada filmnya yang kedua "A Game of Shadows" yang konotasinya ada sebuah game maut padahal yang dimainin catur. Nah disini juga serupa risknya, Suatu "Game maut" yang ternyata cuma sambung kata. Oiya, sebelumnya nama soal ini maunya "A Game of Shadows"
Yu-Gi-Oh! = Di desc soal ini, hanya berfungsi sebagai "bumbu" doang. Game kartu Yu-Gi-Oh! itu masa SMPku :). Walaupun udah gak dikasi main lagi karena dikira judi, aku tetep ikutin kok meta terupdatenya di youtube sampe sekarang (spyral, pendulum magician, dkk).
 |
| maunya respon terhadap soal ini sama seperti responku kalau kartu ini diaktifkan kesel banget |
Urutan kemunculan refrencenya juga ngaruh. Yu-Gi-Oh! muncul duluan karena aku paling pertama terekspos ke itu, trus anime, trus baru Sheclock Holmes. "Porsinya" juga ngaruh. Di soalnya paling banyak ngomongin tentang porsi animenya, karena aku sampe sekarang masih nonton anime, trus Ada sedikit bumbu Yu-Gi-Oh! di bagian atas deskripsi karena masih ngikutin di youtube, trus ada Sherlock Holmes refrence dikit (yang mungkin orang ga nyadar kalau ga kukasi tau) karena aku udah selesai baca semua bukunya taun lalu dan ga baca lagi karena masih ingat dengan jelas. Ada beberapa easter egg lagi sih, seperti kenapa namanya Mawar. Tapi itu dibiarkan inside jokes saja.
sekian unsur intristiknya. Semoga setelah baca, problemku menjadi lebih menarik :). Maaf apabila ada soal yang kurang berkenan seperti PR Maut (Marahin Vince) atau Sinister Shadow Games, atau kalau soalnya "alay". Itu semua sudah direncanakan sesuai dengan tema TOCnya yaitu Kidz Jaman Now.
aku akhiri dengan quotes ini kali:
Midoriya: "Those weren't just random problems either, They're targeted, and every single one of them, is more than a hundred percent of his power"
gg
ReplyDeleteide yang lebih jahat untuk Div 2 D : taruh tricky case yang n==2 di TC pertama :v
ReplyDelete*p.s : aku ga AC gara" tricky case itu -_-
Gaapa :) mudah-mudahan soal soalnya bisa dipakai pembelajaran untuk kedepannya
Deleteeh ada ya bunga Jebret? :'v
ReplyDeleteenggak... nama bunga hanya untuk 1 tokoh per soal :)
Delete