Sabtu, 09 Mei 2020

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:

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

Minggu, 03 Mei 2020

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.

Kamis, 30 April 2020

Pembahasan Semifinal JOINTS PCS 2019

Soalnya dapat Anda cek di https://tlx.toki.id/problems/joints-2019-pcs-semifinal.
Seperti biasa, coba kerjakan sendiri dulu sebelum membaca tulisan ini.


Coin Exchange

Maksud soal ini adalah mencari nilai terkecil dan terbesar yang berada di antara 1 dan N (eksklusif), sehingga nilai tersebut saling prima dengan N. Sebenarnya kondisi ini tidak menjamin seluruh nilai tukar bisa direpresentasikan. Misalnya untuk N=100, nilai terkecil yang saling prima dengannya adalah 3. Meskipun demikian, kita tidak bisa menggunakan 100 dan 3 untuk transaksi senilai 1, 2, 4, 5, 7, 8, dsb.

Untuk mencari bilangan yang saling prima, cukup periksa dari 2 sampai N-1 untuk bilangan yang FPB-nya dengan N sama dengan 1. Begitu ditemukan, langsung hentikan pencarian. Nilai inilah yang menjadi nilai terkecil. Lakukan cara serupa dengan pencarian dari N-1 sampai 2 untuk mencari nilai terbesarnya. Terakhir, cetak selisih mereka.

Solusi ini terkesan \(O(N)\), tetapi sebenarnya jauh lebih cepat dari itu. Sebab sangat besar kemungkinan \(N-k\) untuk \(k\) yang cukup kecil mengakibatkan FPB-nya dengan N sama dengan 1. Sebagai contoh, nilai 99 sudah saling prima dengan N=100. Demikian pula 1000000 dan 999999.


Hitung Kata

Ini soal DP yang cukup sederhana. Idenya seperti longest common subsequence (LCS), tetapi kali ini seluruh karakter di string kedua wajib dicocokkan. Apabila berhasil dicocokkan, tambahkan kemungkinan jawaban dengan 1.

Misalkan kedua string memiliki indeks yang dimulai dari 1. Seperti pada LCS, kita proses karakter demi karakter dari belakang.
Jika \(f(i, j)\) menyatakan banyaknya subsequence dari \(S[1..i]\) yang sama dengan \(P[1..j]\), maka pilihannya adalah:
  • Buang \(S[j]\), sehingga banyaknya cara pencocokan menjadi \(f(i-1, j)\).
  • Cocokkan \(S[i]\) dengan \(P[j]\), sehingga banyaknya cara pencocokan mejadi \(f(i-1, j-1)\). Pilihan ini hanya tersedia kalau \(S[i] = P[j]\).
Base case dicapai apabila:
  • \(j\) bernilai 0, yang artinya pencocokan berhasil.
  • \(i\) bernilai 0, tetapi \(j\) bukan 0, yang artinya pencocokan tidak berhasil.
Secara matematis, bisa dituliskan:
\[ f(i,j) = \left\{\begin{array}{ll}
1 & ,j = 0\\
0 & ,i=0 \land j>0\\
f(i-1,j) + f(i-1,j-1) & ,S[i]=P[j]\\
f(i-1,j) & ,S[i] \ne P[j]\\
\end{array}\right. \]
Sebelum mengimplementasikannya, saya menyadari kalau tidak ada modulo. Lalu saya bertanya-tanya apakah jawabannya muat ditampung dalam integer 64 bit. Jawaban terbesar dicapai apabila \(S\) berisi 'A' sebanyak 1000 karakter, dan \(P\) berisi 'A' pula sebanyak 10 karakter. Jawabannya adalah 1000 kombinasi 10, yang mana melebihi batas atas integer 64 bit.

Karena malas menggunakan big integer, saya coba submit saja. Ternyata accepted :))
Kompleksitas solusi ini \(O(|S||P|)\).


Kerja Pak Blangkon

Observasi yang penting adalah setiap pekerjaan dapat diselesaikan dalam 1 hari, sehingga pekerjaan yang lebih menguntungkan pasti dipilih terlebih dahulu.

Senin, 27 April 2020

Pembahasan Penyisihan JOINTS PCS 2019

Sempat ada laporan kalau ada masalah konfigurasi di soal-soal JOINTS 2019 yang dipasang di TLX. Sambil diperbaiki satu per satu, saya sekalian membaca soalnya. Berhubung soal-soalnya menarik, jadinya saya kerjakan dan akan saya bahas di sini.

Soalnya dapat Anda temui di web TLX: https://tlx.toki.id/problems/joints-2019-pcs-penyisihan

Sangat dianjurkan bagi Anda untuk mencobanya terlebih dahulu. Kalau tersendat baru liat pembahasan di sini :-)

Kode solusi saya cantumkan di akhir tulisan.


Dolan 2019

Deskripsi soal inilah yang membuat saya tertarik mengerjakan seluruh set soal.

Cukup proses setiap barisnya satu per satu sambil mencatat kategori jawaban terbaik sejauh ini. Supaya mudah, kodekan kategori jawaban sebagai berikut:
0. BALIK AJA
1. TERPAKSA
2. SENANG

Awalnya inisialisasi kategori jawaban dengan 0 (untuk "BALIK AJA"). Untuk setiap baris, lakukan iterasi dari kiri ke kanan sambil mencatat:
  1. Karakter terakhir sebelum 'O'. Simpan karakter ini di variabel "prev".
  2. Banyaknya karakter 'O' konsekutif sampai sejauh ini. Anggap banyaknya ini disimpan di variabel "count".
Setiap kali ditemukan karakter yang bukan 'O', simpan karakter itu di variabel "next" dan periksa apakah:
  1. count ≥ N+2. Kalau iya, berarti geng CJ pasti bisa "SENANG".
  2. count ≥ N+1. Kalau iya, periksa apakah salah satu dari prev atau next bernilai 'L'. Kalau iya berarti mereka  "SENANG", dan kalau tidak berarti kategori 1 menjadi kandidat jawaban.
  3. count = N dan nilai dari prev dan next sama-sama 'L'. Kalau iya berarti "SENANG", dan kalau tidak berarti kategori 1 menjadi kandidat jawaban.
Jangan lupa melakukan pemeriksaan kalau sudah mencapai ujung kanan kolom dan karakternya masih juga 'O'. Asumsikan saja next bernilai 'L'.

Terakhir, tinggal cetak kategori jawaban terbaik. Kompleksitas solusinya \(O(RC)\).


KPK

Solusi brutal jelas akan mendapat TLE, berhubung \(3^N\) dengan \(N=10^6\) terlalu besar.

Pertama, coba kita cari KPK dari suatu bilangan \(x\) dengan \(3^N\). Kita dapat menyatakan \(x\) sebagai perkalian dari suatu bilangan \(k\) dengan \(3^p\), sedemikian sehingga \(k\) tidak lagi mengandung faktor 3:
\[x = k 3^p\]
Mengingat masa SD, KPK dari \(k 3^p\) dan \(3^N\) adalah \(k 3^N\).
Bila \(x\) dimulai dari 1 sampai dengan \(3^N\), maka nilai yang ingin dicari adalah:
\[ \begin{array}{c} k_1 3^N + k_2 3^N + k_3 3^N + ... + k_{3^N} 3^N
\\ = 3^N (k_1 + k_2 + k_3 + ... + k_{3^N} ) \end{array} \]