Teknik Optimisasi Konstanta

Akhir-akhir ini saya sering berlatih di SPOJ, dan seringkali sudah menggunakan algoritma optimal, tetapi tetap TLE. Akibatnya saya harus melakukan optimisasi konstanta habis-habisan hingga akhirnya mendapat AC.

Pada competitive programming, konstanta sering dianggap menjadi hal yang kecil. Karena kecil, dianggap tidak mempengaruhi performa secara keseluruhan. Memang benar, saya termasuk yang berpikiran seperti itu. Namun hal ini tidak selalu berlaku apabila konstanta yang kecil itu ada dalam jumlah yang besar. Bayangkan jika harga beras awalnya Rp 1,00 per butir, lalu tiba-tiba naik menjadi Rp 1,12 per butir. Mungkin memang kenaikannya hanya Rp 0.12, tetapi bila kita membeli 1 ton beras yang isinya ada 36.590.000 butir beras, kenaikannya menjadi Rp 4.390.800,00. Hal yang sama juga berlaku pada program, bila konstanta yang kecil itu muncul pada looping yang bisa dilakukan ratusan ribu kali, bisa saja akan mempengaruhi performa program secara signifikan.

Biasanya, Anda hanya memerlukan optimisasi konstanta pada kompetisi ACM-ICPC (biasanya bukan Jakarta) atau mengerjakan soal di online judge. Untuk kompetisi seperti OSN atau IOI, sang pembuat soal sudah menentukan time limit secara bijaksana sehingga solusi dengan perbedaan konstanta yang bisa dimaklumi tetap mendapatkan AC. Bisa jadi time limit yang ditentukan berasal dari 10 dikali waktu eksekusi solusi si pembuat soal.

Pengalaman saya dalam pemrograman terus menambah pengetahuan dalam melakukan optimisasi konstanta. Berikut ini saya jabarkan teknik-teknik yang saya ketahui, dan siapa tahu dapat membantu Anda di kemudian hari. Sebagai catatan, berkat optimisasi konstanta (dan keberuntungan) saya berhasil menyelesaikan soal Alien Abduction Again, soal ICPC Jakarta 2013 dan berkat itu tim saya (Vidina 2.0) berhasil menjadi best local team :)

SPOJ FSHEEP - Fencing in the Sheep

Soal ini saya hadapi pada saat latihan Pelatnas 2 TOKI 2011. Saya benar-benar tidak bisa mengerjakannya pada saat itu. Akhirnya saya kembali pada saat Pelatnas 4 TOKI 2011, dan berhasil membalas dendam dengan menyelesaikan soal ini >:-)

Dari deskripsi soalnya, terlihat bahwa soal ini cukup sederhana: diberikan sebuah poligon yang mungkin tidak konveks dan sejumlah titik. Tentukan banyaknya titik yang ada di dalam poligon!

Memeriksa apakah suatu titik berada di dalam poligon bisa dilakukan dengan algoritma ray casting, yaitu dengan membuat segmen garis imajiner dari titik tersebut ke suatu arah sembarang, lalu hitung berapa kali garis itu berpotongan dengan poligon. Bila genap, artinya titik berada di luar poligon dan bila ganjil, artinya titik berada di dalam poligon (tidak percaya? Cobalah!). Sayangnya algoritma ini agak repot dilakukan karena garis imajiner yang dibuat tidak boleh menyentuh titik sudut pada poligon. Lagipula kompleksitas untuk sekali pemeriksaan adalah O(N), padahal poligon yang diberikan bisa memiliki sisi sebanyak 100.000, dan banyaknya titik juga bisa sampai 100.000.

Bila tidak ada properti khusus pada soal ini, maka sepertinya soal ini mustahil untuk diselesaikan. Beruntungnya, ada sebuah kalimat yang sangat penting pada soal: "Exhausted, he moves to a place within the pen from which he can see the whole interior of the pen (without any fence getting in the way) and begins to count the sheep which are within it."

Artinya, dijamin ada sebuah titik yang mana bila seseorang berdiri di sana, dia bisa melihat seluruh isi poligon (kemudian diberitahu bahwa titik tersebut ada di (0,0)). Berikut ini gambar yang memberi ilustrasi jenis poligon tersebut. Poligon di sebelah kiri merupakan poligon yang valid, dan yang kanan tidak karena daerah yang berwarna coklat tidak bisa dilihat:

Komposisi Struktur Data Dynamic Range Query

Sejauh ini saya sudah pernah membahas struktur data:

• Disjoint-set
• Segment tree[2] [3]
• Binary Indexed Tree
• Treap [1]

Ada juga struktur data yang menarik untuk digunakan:

• BBST (AVL tree atau Red-Black Tree)
• Segment array [1]
• Range tree [1] (sering diimplementasikan sebagai segment tree dengan nilai agregat berupa vector)

Dan ada juga struktur data yang lebih jarang digunakan:

• Kd Tree
• Quad Tree
• Interval Tree

Masing-masing struktur data tersebut memiliki peran dan kegunaan masing-masing. Oleh karena itu, ketika sedang mengerjakan soal dynamic range query non-klasik, pertanyaan yang muncul adalah "dikerjakan pakai struktur data apa ya?"