Menutup Poligon

Phew, baru sempet nulis lagi...

Aslinya banyak yang terjadi, kayak kesalahan konyol di Kickstart Round A, kehidupan kuliah yang tambah broken, sama kegeblekan lainnya. Cuma kayaknya sekarang mau fokus nulis tentang salah satu soal yang kuurus di TOKI Open Contest Maret 2018, Menutup Poligon (Sulit & Mudah).

Jadi kalau mungkin belum sadar, di pengumuman TOC, ada namaku nongol di belakang. Yep, mulai bulan ini, aku juga ikut jadi panitia TOC. Bantu ngurus-ngurus gitu. Moga aja gak jadi beban T_T Btw, dari panitia TOC cuma aku yang sekarang domisilinya di Indonesia :")

Buat TOC kemaren, sebenernya aku ngurus testcase buat 3 soal, yakni Menutup Poligon (Sulit & Mudah), sama Lapangan Tembak (Sulit). Walaupun sebenernya jadi kayak ngurus 4 soal, karena runner Lapangan Tembak (Sulit) juga diedit jadi versi mudah-nya, sama Ammar tapi. Tapi well, mari fokus ke soal yang bikin testcase-nya itu kayak neraka.

Oiya, tulisan di bawah mungkin aja mengandung spoiler ya. Sudah saya tulis warning di sini :P

Btw, ini cara aku buat testcase. Kalau ada cara yang lebih elegan (dan aku sangat berharap ada), bisa komentar di bawah :D

Jadi, soal versi sulit kan intinya ngecek bisa tutup pake persegi 2 x 2. Nah, cuma gimana caranya bisa bikin testcase yang ukurannya besar, dan jawabannya "YA"?  Yang pertama kepikiran sih jelas, bikin persegi 2 x 2 yang nempel-nempel. Jadi pertama bikin grid, terus pasang-pasang persegi. Kalo udah,  transformasi grid-nya jadi format masukan yang diminta. Idenya sih gitu.

Cuma, pertama-tama, sebelum aku ngoding itu....
Aku harus bikin validator constraint-nya.
Terus aku gak tau caranya ngecek poligon gak ada motong diri sendiri selain dalam O(N^2).
Mantap gan.

Berhubung soal ini harusnya gak perlu bikin testcase yang banyak garis miringnya, aku jadinya bikin 4 pengecekan: motong horizontal-horizontal, vertikal-vertikal, horizontal-vertikal, sama garis miring-bebas. 3 Pertama bisa O(N log N), yang terakhir O(garis_miring * N). Jadi selama garis miringnya gak banyak, harusnya ngeceknya gak lama. Cuma ini ngodingnya neraka :"""

Oiya, kalo ada yang tau cara ngecek apakah poligon gak ada motong diri sendiri yang cepet, mungkin bisa komentar di bawah juga :"""

Nah, setelah bikin validator constraint, balik ke bikin jawaban "YA" yang gede.

Aku pertama bikin cara transformasi grid-nya jadi poligon, sesuai format masukan. Sebenernya gak terlalu susah, cuma nelusurin sisi-sisi poligon menurut arah jarum jam doang. Agak hardcode sih, nanganin jalan sama beloknya. Gak terlalu susah, cuma ngerasa ini bisa jadi 1 soal sendiri.

Habis meyakini transformasinya dah bener, aku bikin generator nempel-nempel persegi 2 x 2. Iseng, cek kalo perseginya 5, bisa. Langsung hajar gede, coba perseginya 50.000. Gagal, ada constraint yang dilanggar. Ada titik yang muncul 2 kali di input. Hmmm, harusnya gak mungkin gini. Coba perseginya 10. Gak gagal, tapi jawabannya "TIDAK".

wat. wat. wat. wat.

Aku coba cetak poligon sama petak-petak grid yang ditempeli persegi. Hasilnya kayak gini:

Yang disilangin itu petak yang ditempeli persegi. Pas sadar ada petak bolong, yakni petak yang dihitamkan itu, rasanya:

Jadi ya, intinya gak bisa main tempel sembarangan aja. Aku harus periksa juga apakah dengan masang itu, bakal bikin "lubang" di poligon akhirnya. Jadi yang begini ya gak boleh:

Cuma gimana coba ngeceknya? Berhubung "lubang"-nya bisa ukurannya apa aja, aku cuma kepikiran flood-fill awalnya, yang gak mungkin feasible kalo untuk bikin testcase. Pusing parah itu.

Cuma gak mungkin nyerah untuk bikin testcase-nya, berhubung TOC-nya udah dekat :"" Jadinya aku coba pikir lagi gimana cara ceknya. Aku curiga bisa dibikin pake properti planar graph. Rasanya dulu pas matdis 2 pernah dapet formula terkait vertex, edge, sama face di planar graph. Terus nemu laman di Wikipedia terkait itu.

Jadinya aku coba modelkan jadi  planar graph: anggap petak 1 x 1 itu 1 vertex. Lalu, buat edge di antara 2 vertex yang bersebalahan dan udah ditempeli. Aku bisa itung face yang berupa persegi 2 x 2. Kalau gak ada "lubang", harusnya total face yang bisa kuitung itu sama dengan v - e + f = 1, dikurangi satu karena ada face di luar grafnya. Misal untuk gambar di atas, graf-nya artinya begini:

Ada 12 vertex, 16 edge, sama 4 face persegi 2 x 2. Tapi, 12 - 16 + 4 = 0, artinya ada satu face yang gak kuitung, yakni yang di tengah. Maintain banyak vertex, edge, sama face gak terlalu susah. Artinya, secara ajaib aku bisa nanganin agar tidak ada "lubang".

Jadi ini rasanya mendapatkan pencerahan.

Habis aku tambahin pengencekan itu, code-ku udah berantakan banget. Aku coba generate testcase lagi.

Gagal. Ada titik yang muncul 2 kali di poligon.

Jadi ini rasanya frustrasi.

Aku coba cetak poligonnya lagi. Kurang lebih begini potongannya:

intinya gambar yang di tengah

Pas liat gambar kurang lebih ngeh sih. Jadi, ada 2 petak yang sharing sudut doang (yang ditandai titik di atas), bikin "lubang" lagi. Bingung sih ini harus diapain. Cuma firasatku, cukup cek apakah ada petak yang sharing sudut doang udah cukup, karena kalo nggak sudut doang, "lubang" pasti kena kasus planar sebelumnya. Pas dicoba, udah gak ada yang gagal lagi. Yey!

Setelah bikin untuk nempel-nempel 2 x 2, aku juga bikin untuk nempel 1 x 1, karena bakal berguna untuk bikin testcase invalid dan bikin testcase versi mudah soal ini. Setelah itu, aku juga bikin fungsi buat hapus sembarang titik, niatnya biar poligonnya jadi punya garis miring. Cuma ngebug-ngebug, hingga akhirnya jalan. Ini fungsi dibutuhin soalnya buat versi mudah dari soal ini.

Habis itu, nambahin testcase manual dari Ammar, sama pattern pemasangan persegi dari Jonmul. Udah beres, sisa di-review. Pas review, baru sadar kalo validator perpotongan vertikal-vertikal sama horizontal-horizontal ngebug T_T Jadinya beberapa testcase manual Ammar lolos. Habis benerin validator, testcase-nya Ammar jadi harus diubah dikit. Udah deh.

Btw, ini gak tau gimana rasanya yang nge-review. > 1000 baris. Sebenernya bisa aja di-refactor karena beberapa fungsi mirip, cuma otakku udah overheat. Parah. Btw, untuk versi mudah sih gak terlalu susah begitu yang versi sulit udah jadi. Tinggal comot validator, masang 1 x 1, sama hapus titik.

Habis entah gimana caranya ini runner bisa lolos review, soalnya dipasang. Di kontesnya, soal ini mayan berdarah-darah hasilnya.

Gak papa, yang bikin testcase-nya juga berdarah-darah kok. Seenggaknya ada 3 soal di pembuatan testcase-nya: solusi-nya, transformasi grid ke poligon, sama cek planar. Ini juga gak ngitungin soal ke-4, ngecek validitas testcase.

Sampai sekarang, kayaknya ini soal paling berdarah-darah yang pernah kuurus deh. Semoga gak ngurus soal beginian hingga beberapa waktu lagi :""

Mungkin sekian aja kali ya, sampai bertemu di post selanjutnya :D