Solusi Soal A Kontes Hello 2018 Codeforces

Bismillaah.

Halo pembaca semua! Apa kabar? Semoga sehat ya, terutama setelah membaca pos ini semoga semakin mual-mual sehat jasmani dan rohani.

Pos ini membahas salah satu soal kontes yg diadakan di Codeforces kemarin. Buat yang belum tau apa itu Codeforces, situs tersebut adalah situs untuk berlatih soal-soal pemrograman yang mengedepankan kemampuan problem solving. Oke, langsung aja yaa pembahasannya.

Soal lengkap ada di sana. Buat yang males buka tautannya, berikut deskripsi soalnya secara sederhana.

Diberikan bilangan bulat n dan m. Tentukan nilai dari m di-modulo dengan 2n.

Batasan :

  • 1 ≤ n ≤ 10
  • 1 ≤ m ≤ 108
  • Batas waktu 1 detik

Cara Naif

Hitung 2n dengan perulangan biasa, kemudian hitung m modulo 2n dengan modulo secara langsung.
Kompleksitas algoritma ini sebesar O(n), kemungkinan besar cukup berhasil dengan batas waktu 1 detik dan nilai n yang paling besar adalah 108.

Tapi permasalahan lain muncul : bahasa pemrograman apa yang cukup muat menyimpan bilangan yang maksimal sebesar 2100000000 untuk menghitungnya? Mungkin Python bisa, tapi untuk bahasa yang akan overflow jika menyimpan data sebesar itu, akan kita coba cara lain.

Analisis Permasalahan

Analisis ini dilkaukan untuk mengatasi overflow pada beberapa bahasa pemrograman. Jika kita perhatikan, ada saatnya nilai 2n akan selalu lebih besar dari berapapun nilai m, bahkan untuk m paling besar sekalipun (yaitu 108). Misalkan nilai n yang mengakibatkan hal ini adalah k. Dengan mencari nilai k ini, kita bisa membatasi algoritma kita di atas, yaitu dengan cara :

  1. jika n > k, langsung keluarkan nilai m
  2. jika sebaliknya (jika n ≤ k), langsung keluarkan nilai m modulo 2n.

Lalu bagaimana cara kita mencari nilai k tersebut?
Secara matematis, nilai k yang akan kita cari adalah bilangan bulat k terbesar yang memenuhi pertidaksamaan 2k < 108.

(Haduh admin nyesel pas pelajaran pertidaksamaan SMA ga nyimak :'( Jadi jangan bilang kalo matematika ga berguna yaa kids!)

Oke lanjut, pertidaksamaan tersebut ternyata ekuivalen dengan pertidaksamaan k < log2 108. Lebih jauh, ekuivalen dengan

k < 8 * log2 10
= 8/(log 2)
= 8/0,3
= 80/3

Didapat bahwa k < 80/3 atau k < 26,…
Karena tadi kita mencari bilangan bulat k terbesar yang memenuhi, tentu didapat nilai k = 26.

Yasss, we got it! Tinggal kita implementasikan analisis kita tadi dalam bahasa pemrograman kalian. Ini hasil implementasi admin.

Dengan begitu, algoritma baru yang kita dapat dari hasil analisis tadi juga memiliki kompleksitas sebesar O(n) untuk n ≤ 26 dan O(1) untuk n > 26, yang insyaa Allaah akan mendapat verdict ACCEPTED.


Inti dari pembahasan ini sebenarnya cukup sederhana. Sedikit analisis mendalam terhadap soal yang ada akan membawa dampak yang besar pada solusi kita. Analisis yang ada pada soal ini termasuk cukup dasar untuk dipelajari dalam bidang algoritma atau pemrograman kompetitif. Hanya saja, untuk terbiasa menganalisis soal ini memerlukan waktu yang tidak singkat. Perlu banyak latihan untuk membiasakan diri dan meningkatkan jam terbang kita. Tetap semangat belajar demi meraih jodoh idaman cita-cita.

Tinggalkan Balasan