Aftermath dan Beforemath Mario di ISMOC.
Beberapa hari yang lalu, saya mengajukan sebuah soal di lomba ISMOC, yang ternyata semalam sebelum lomba, diberi counter-example oleh Erlang Wiratama Surya T_T. Tapi untungnya kita beri sebuah phrase sehingga bisa dikerjakan.
Karena soalnya berasal dari sebuah argument extermal (karena saya bikin soalnya pakai argument dulu, trus ditambah macam-macam baru jadi soal), akhirnya kita memberikan tambahan kata-kata pada soalnya agar argument extermal saya tetap jalan. Tambahannya cukup minim yaitu ""beserta sebuah kanal dari $G$ ke $X$"" seperti pada soal dibawah (huruf tebal menyatakan ralat yang ditambahkan).
Walaupun sebenarnya, karena sudah mengantuk, kita melakukan argument ekstermal pada directed graph menggunakan arah yang berbeda dengan yang diberikan soal, dan untungnya suatu struktur pada soal merupakan sebuah cycle, jadi pada akhirnya arahnya tidak begitu ngaruh, dan soal masih benar, ini hoki maksimal sih :p.
Saya minta maaf atas kesalahan ini, dan berterima kasih kepada Erlang yang sudah mau berdiskusi sampai jam 2 subuh pada malam sebelum lomba.
Pada saat lomba, terdapat dua orang yang berhasil menyelesaikan soal ini dengan sempurna.
Solusi (Outline) : Pertama-tama buktikan dulu ketika Mario stuck di suatu kota, yakni sudah tidak bisa kemana-mana lagi, maka pasti kota itu adalah kota $X$. Jadi pipa spesial yang masuk dan keluar kota $X$ sudah dipakai. Jika ada pipa yang belum dipakai, pilih pipa spesial $A$ ke $B$ yang belum terpakai dengan $B$ paling jauh ke $X$, maka nanti diperoleh pipa spesial dari $B$ juga belum terpakai, kontradiksi dengan $B$ paling jauh.
Yang jadi masalah adalah struktur pipa spesial pada soal, yang akhirnya kita ubah pada soal diatas menjadi cycle.
Berikut adalah beberapa versi soal :
1. (Sebelum Ralat) Struktur pipa spesial pada soal adalah directed path dari $X$ ke $G$ yang memuat semua kota.
2. (Setelah Ralat) Struktur pipa spesial pada soal adalah directed cycle yang memuat semua kota.
3. (Awal ketika buat) Struktur pipa spesial pada soal adalah directed path dari $G$ ke $X$ yang memuat semua kota.
Perhatikan bahwa yang membedakan 1 dan 3 itu hanya arah saja (mungkin dulu saya lupa bahwa ketika efek P-Switch habis, maka pipa spesialnya kembali ke arah semua juga.)
Versi 1 tidak berkerja karena ketika $B$ terjauh, belum tentu ada pipa spesial bermula dari $B$.
Versi 3 harusnya tetap berkeja, namun ceritanya akan sedikit ribet, dan soal sekarang saja sudah panjang (Saya baru nyadar bahwa sebenarnya cukup bilang, pipa spesial ga balik lagi ke arah awal).
Ketika saya melihat kembali ketikan saya beberapa bulan lalu, ternyata saya menggunakan argument "$B$ paling dekat ke $X$" , sepertinya saya melakukan argument nya dengan asumsi bahwa pipa spesial arahnya tetap sama ketika P-Switch ditekan lagi.
Anyway, soal diatas merupakan adaptasi dari sebuah Algoritma untuk mendeteksi Eulerian Cycle pada sebuah graph simple, yang disebut Fleury's Algorithm. Algoritma yang saya tahu berkerja di Graph Simple, yaitu dengan melihat sebuah struktur subgraph berupa "bridge". Nantinya edges yang berada pada bridge ini akan digunakan sebagai last resort ketika mencari Eulerian Cycle.
Saya mencoba mengerjakan Algoritma serupa ketika Graph yang diberikan adalah Graph berarah, namun disini, agar terdapat Eulerian Cycle, saya beri kondisi in degree sama dengan out degree (yang ini saya jadiin soal Final ISMOC SMP :p ).
Sayangnya meskipun dengan syarat in-degree dan out-degree, saya masih belum bisa menemukan struktur yang cocok untuk "bridge" di directed graph. Setelah beberapa lama, saya menggunakan argument ekstermal diatas, dan ambil asumsi malas bahwa bridge nya berbentuk garis saja. (yang akhirnya diubah menjadi cycle, karena phrase minim yang dibutuhkan).
Kira-kira struktur general subgraph spesial untuk Fleury's Algortihm versi directed graph ini apa ya?
Karena soalnya berasal dari sebuah argument extermal (karena saya bikin soalnya pakai argument dulu, trus ditambah macam-macam baru jadi soal), akhirnya kita memberikan tambahan kata-kata pada soalnya agar argument extermal saya tetap jalan. Tambahannya cukup minim yaitu ""beserta sebuah kanal dari $G$ ke $X$"" seperti pada soal dibawah (huruf tebal menyatakan ralat yang ditambahkan).
Walaupun sebenarnya, karena sudah mengantuk, kita melakukan argument ekstermal pada directed graph menggunakan arah yang berbeda dengan yang diberikan soal, dan untungnya suatu struktur pada soal merupakan sebuah cycle, jadi pada akhirnya arahnya tidak begitu ngaruh, dan soal masih benar, ini hoki maksimal sih :p.
Saya minta maaf atas kesalahan ini, dan berterima kasih kepada Erlang yang sudah mau berdiskusi sampai jam 2 subuh pada malam sebelum lomba.
Pada saat lomba, terdapat dua orang yang berhasil menyelesaikan soal ini dengan sempurna.
Mario sedang berada pada Negeri Jamur yang mempunyai $n$ buah kota. Beberapa dari kota tersebut terhubung oleh saluran pipa yang mempunyai arus satu arah, pipa-pipa ini dapat digunakan sebagai sarana transportasi antar kota, namun Mario tidak bisa berpindah melawan arus pada pipa-pipa tersebut, sehingga setiap pipa hanya berlaku sebagai jalan satu arah. Diketahui bahwa untuk setiap kota, banyak pipa dengan arus menuju keluar kota sama banyak dengan banyak pipa dengan arus menuju masuk ke kota tersebut.Suatu hari pada kota $P$, Mario menekan tombol P-Switch yang menyebabkan semua arus pipa pada Negeri Jamur berbalik arah, yakni pipa dengan arus dari kota $a$ ke kota $b$ berubah menjadi pipa dengan arus dari kota $b$ ke kota $a$. Kemudian dimulai dari kota $P$, Mario berkelana ke kota-kota dengan menggunakan arus pada pipa-pipa tersebut. Setelah efek P-Switch habis, semua arah arus pipa kembali seperti semula dan pada saat itu Mario sudah berada di kota $X$ dan telah mengunjungi semua kota tepat sekali dengan menggunakan tepat $n-1$ buah pipa, sebutlah $n-1$ buah pipa yang telah dilalui Mario tersebut (beserta sebuah kanal dari $G$ ke $X$) sebagai pipa spesial, dan pipa yang lain sebagai pipa tak-spesial.Misalkan dimulai dari kota $X$, Mario akan menutup pipa-pipa pada Negeri Jamur dengan berkelana ke kota-kota melalui pipa-pipa tersebut dengan aturan berikut:
- Apabila sebuah pipa telah dilalui oleh Mario, maka pipa tersebut langsung dia tutup dan tidak bisa dilalui lagi.
- Pada setiap kota, Mario akan memilih keluar melalui pipa spesial hanya jika semua pipa tak-spesial yang menuju keluar dari kota tersebut sudah ditutup.
Buktikan bahwa dengan aturan diatas, (apapun pilihan Mario) ketika Mario sudah tidak bisa berpindah kota, maka pada saat itu dia sedang berada kembali di kota $X$ dan telah menutup semua pipa pada Negeri Jamur.
Solusi (Outline) : Pertama-tama buktikan dulu ketika Mario stuck di suatu kota, yakni sudah tidak bisa kemana-mana lagi, maka pasti kota itu adalah kota $X$. Jadi pipa spesial yang masuk dan keluar kota $X$ sudah dipakai. Jika ada pipa yang belum dipakai, pilih pipa spesial $A$ ke $B$ yang belum terpakai dengan $B$ paling jauh ke $X$, maka nanti diperoleh pipa spesial dari $B$ juga belum terpakai, kontradiksi dengan $B$ paling jauh.
Yang jadi masalah adalah struktur pipa spesial pada soal, yang akhirnya kita ubah pada soal diatas menjadi cycle.
Berikut adalah beberapa versi soal :
1. (Sebelum Ralat) Struktur pipa spesial pada soal adalah directed path dari $X$ ke $G$ yang memuat semua kota.
2. (Setelah Ralat) Struktur pipa spesial pada soal adalah directed cycle yang memuat semua kota.
3. (Awal ketika buat) Struktur pipa spesial pada soal adalah directed path dari $G$ ke $X$ yang memuat semua kota.
Perhatikan bahwa yang membedakan 1 dan 3 itu hanya arah saja (mungkin dulu saya lupa bahwa ketika efek P-Switch habis, maka pipa spesialnya kembali ke arah semua juga.)
Versi 1 tidak berkerja karena ketika $B$ terjauh, belum tentu ada pipa spesial bermula dari $B$.
Versi 3 harusnya tetap berkeja, namun ceritanya akan sedikit ribet, dan soal sekarang saja sudah panjang (Saya baru nyadar bahwa sebenarnya cukup bilang, pipa spesial ga balik lagi ke arah awal).
Ketika saya melihat kembali ketikan saya beberapa bulan lalu, ternyata saya menggunakan argument "$B$ paling dekat ke $X$" , sepertinya saya melakukan argument nya dengan asumsi bahwa pipa spesial arahnya tetap sama ketika P-Switch ditekan lagi.
Anyway, soal diatas merupakan adaptasi dari sebuah Algoritma untuk mendeteksi Eulerian Cycle pada sebuah graph simple, yang disebut Fleury's Algorithm. Algoritma yang saya tahu berkerja di Graph Simple, yaitu dengan melihat sebuah struktur subgraph berupa "bridge". Nantinya edges yang berada pada bridge ini akan digunakan sebagai last resort ketika mencari Eulerian Cycle.
Saya mencoba mengerjakan Algoritma serupa ketika Graph yang diberikan adalah Graph berarah, namun disini, agar terdapat Eulerian Cycle, saya beri kondisi in degree sama dengan out degree (yang ini saya jadiin soal Final ISMOC SMP :p ).
Sayangnya meskipun dengan syarat in-degree dan out-degree, saya masih belum bisa menemukan struktur yang cocok untuk "bridge" di directed graph. Setelah beberapa lama, saya menggunakan argument ekstermal diatas, dan ambil asumsi malas bahwa bridge nya berbentuk garis saja. (yang akhirnya diubah menjadi cycle, karena phrase minim yang dibutuhkan).
Kira-kira struktur general subgraph spesial untuk Fleury's Algortihm versi directed graph ini apa ya?
Post a Comment: