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:
\[ 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|)\).
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:
Secara matematis, bisa dituliskan:- \(j\) bernilai 0, yang artinya pencocokan berhasil.
- \(i\) bernilai 0, tetapi \(j\) bukan 0, yang artinya pencocokan tidak berhasil.
\[ 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.
