Bekerja dengan Logaritma

Persoalan motivasi:

1. Diberikan dua bilangan bulat a dan b (1 ≤ a, b ≤ 10⁸). Apa tiga digit pertama dari a^b?
2. Diberikan sebuah bilangan bulat N (1 ≤ N ≤ 10⁵). Tentukan banyaknya digit dari N faktorial!
3. Diberikan sebuah bilangan bulat N. Tentukan K, sedemikian sehingga N^K lebih kecil dari K faktorial!
4. Diberikan sebuah bilangan genap n. Tentukan \(\displaystyle \frac{C^{N}_{N/2}}{2^N}\)!

Bagaimana melakukan komputasi semacam itu? Sesuai dengan judulnya, solusinya adalah dengan logaritma.

Dalam pemrograman kompetitif, logaritma memang jarang digunakan. Bila diperlukan, biasanya bukan sebagai inti soal/algoritma utama. Artinya, logaritma bisa jadi seperti perkakas yang dibutuhkan untuk menyelesaikan soal. Tanpa perkakas itu, soal tidak dapat terselesaikan meskipun kita tahu algoritma utamanya. Oleh karena itu saya harap tulisan ini dapat membekali Anda :)

Kisah Perjalanan di TOKI: Bangkit dari Keterbelakangan

Setelah OSN berakhir, hari-hari kembali berlangsung seperti biasa. Kembali ke lingkungan sekolah, menghafal tata nama senyawa karbon, menggunakan mikroskop, dsb. Bedanya hanya saya harus ekstra usaha untuk mengejar segala ketinggalan pelajaran karena ikut OSN. Tidak terlalu bermasalah, karena saya hanya bolos sekitar seminggu saja.

Pelatnas

Tidak lama kemudian, datang surat ke kantor tata usaha, berisi undangan menghadiri Pelatihan Nasional (Pelatnas) 1 TOKI 2010 di Bandung. Pelatnas ini durasinya tiga minggu, yang artinya saya harus bolos kembali. Rasanya lumayan senang karena bisa bertemu lagi dengan teman-teman OSN.

Sesampai di Bandung, ternyata suasana kompetisinya terasa sekali. Ada beberapa orang yang tidak pernah saya jumpai di OSN, mendadak muncul. Mereka dikenal sebagai VETERAN. Jadi orang-orang yang sebelumnya sudah pernah mengikuti Pelatnas, tetapi gagal di suatu tingkat atau berhasil ke IOI, tahun depannya dapat ikut Pelatnas lagi tanpa melalui OSN (tentunya bila mereka masih belum lulus SMA).

SPOJ DOSA - Lalith Dosa

Soal ini sama sekali tidak ada hubungannya dengan "dosa" dari "berdosa". Jangan tanya saya mengapa judul soalnya seperti itu :)

Soal kali ini tergolong baru ditambahkan di SPOJ dan cukup populer. Terlihat sebagai soal yang mudah, tetapi sebenarnya tidak. Banyak orang yang terjebak dan mendapatkan WA, lalu bertanya-tanya di mana letak kesalahannya kepada sang pembuat soal. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.

Salah satu kasus uji mautnya adalah:

12
10 11 12 10 9 15 16 22 21 19 20 21 

Jawaban seharusnya adalah 4.

SPOJ PERIOD - Period

Kebiasaan saya kalau sedang mau mengerjakan soal-soal di SPOJ adalah menatapi halaman status. Jika melihat ada orang melakukan pengumpulan untuk soal yang kodenya menarik, akan saya coba lihat soalnya. Kali ini saya mendapati soal sederhana yang menyenangkan untuk didiskusikan, yaitu tentang string. Sepengalaman saya bertanding, soal string jarang keluar di perlombaan (kecuali ICPC Jakarta).

Inti soalnya sederhana, Anda dapat langsung mengaksesnya di sini. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.

Solusi paling naif adalah dengan mencoba semua kemungkinan prefix, lalu untuk masing-masing prefix dicari periodenya. Seperti biasa, cara ini akan TLE. Untuk mencoba semua kemungkinan prefix saja sudah ada N kemungkinan. Oleh karena itu, untuk mempercepat pendekatan ini setidaknya untuk menghitung periode harus dilakukan dalam O(1).