Petunjuk Coding: Operasi Bit

Beberapa tulisan saya menyinggung tentang operasi pada bit, seperti pada struktur data Binary Indexed Tree dan teknik optimisasi konstanta. Tulisan ini akan membahas semua yang saya ketahui tentang operasi bit. Menguasainya akan membantu Anda dalam implementasi solusi.

---

Representasi Bit

Komputer merepresentasikan angka dalam bentuk bilangan basis 2, atau nama lainnya binary/biner. Representasi ini hanya memiliki angka 0 atau 1.
Sebuah digit pada bilangan biner disebut dengan bit.
Sebagai catatan, bilangan yang kita biasa gunakan adalah basis 10, dengan digit berkisar antara 0 sampai 9.

Perhatikan contoh bilangan biner berikut:

1001101

Digit paling kanan menyatakan banyaknya $2^0$, digit kedua dari kanan menyatakan banyaknya $2^1$, dan seterusnya. Kita dapat mengetahui nilai bilangan tersebut dalam basis 10 dengan menjumlahkan seluruh nilai yang dinyatakan setiap bit:

1 * 2^0 =  1
0 * 2^1 =  0
1 * 2^2 =  4
1 * 2^3 =  8
0 * 2^4 =  0
0 * 2^5 =  0
1 * 2^6 = 64
         ---- +
          77

Kini kita tahu hubungan antar representasi bilangan biner dan basis 10. Hubungan ini hanya berlaku untuk bilangan bulat (integer). Kita tidak membahas tentang bilangan riil, karena bentuk representasinya bergantung pada konteks.

Cara serupa dapat digunakan untuk mengubah bilangan basis 10 ke basis 2. Namun, ada algoritma yang lebih praktis:

?

1 2 3 4 5 6 7 8 9

string toBinary(int v) {   string s = "";   int x = v;   while (x > 0) {     s = to_string(x%2) + s;     x /= 2;   }   return s; }

Prinsip kerja algoritma ini akan Anda ketahui setelah memahami operasi shift right yang akan dibahas di bawah.

Pembahasan Final JOINTS PCS 2019

Tulisan terakhir dari seri pembahasan JOINTS PCS 2019.
Soal-soalnya dapat dilihat dan dicoba di https://tlx.toki.id/problems/joints-2019-pcs-final.

---

Coin Exchange 2

Solusinya mirip dengan soal Coin Exchange pada penyisihan. Cukup coba iterasi dari $N/2$ menuju ke 2. Begitu ditemukan nilai yang FPB-nya dengan $N$ sama dengan 1, hentikan pencarian dan cetak jawaban.

---

Dolan 2020

Pertama, sederhanakan soal dengan menganggap suatu sel berisi 'P' sama dengan 5 sel berisi 'L':

.....       .....
.....       ..L..
..P..   =   .LLL.
.....       ..L..
.....       .....

Sekarang tugas kita tinggal mencari persegi panjang yang sepenuhnya hanya terdiri dari 'O'.
Apabila diproses baris per baris, sadari bahwa soal ini menjadi mirip dengan suatu soal klasik: diberikan sebuah histogram, cari luas persegi panjang terbesar yang sepenuhnya dikandung histogram tersebut.

Misalkan kita memiliki konfigurasi berikut dan sedang memproses baris ketiga. Supaya lebih mudah dilihat, tanda titik menyatakan 'O'.

LL.L..L.
.L....LL
....L...

Dari baris ketiga, struktur ini dapat dipandang seperti histogram berikut, dengan 'X' menyatakan bagian dari batangan histogram.

  X  X
X XX X  
XXXX XXX

Terdapat algoritma $O(N)$ untuk mencari luas persegi panjang terbesar di dalam histogram dengan $N$ batangan. Idenya adalah untuk setiap batangan pada histogram dengan tinggi $h$, cari indeks sekiri dan sekanan mungkin sehingga seluruh ketinggian batangan histogram di antara keduanya $\ge h$. Bila kedua indeks tersebut adalah $a$ dan $b$, berarti luas persegi panjang dengan panjang $h$ dan lebar $(b-a+1)$ menjadi kandidat solusi.

Ilustrasi persegi panjang terbesar yang muat dan setinggi batangan yang berwarna gelap.

Mencari indeks terkiri dan terkanan untuk setiap batangan dapat dilakukan secara efisien dengan bantuan monotonic stack. Gunakan saja stack biasa, yang menyimpan indeks batangan. Syarat khusus yang menjadikannya monotonic adalah tinggi batangan untuk setiap indeks dalam stack wajib menaik.