My first Magazine pemrograman-kompetitif-dasar | Page 26

2 Matematika Diskret Dasar
Secara matematis,
jika ada N ekor burung dan M sangkar, maka pasti ada sangkar yang berisi
 N 
setidaknya M
ekor burung.
Contoh Soal 2.1: Subhimpunan Terbagi
Anda diberikan sebuah array A berisi N bilangan bulat non-negatif. Anda ditantang untuk
memilih angka-angka dari array -nya yang jika dijumlahkan habis dibagi N. Angka di suatu
indeks array tidak boleh dipilih lebih dari sekali.
Apabila mungkin, cetak indeks angka-angka yang Anda ambil. Sementara apabila tidak
mungkin, cetak "tidak mungkin".
Batasan
• 1 ≤ N ≤ 10 5
• Array A hanya berisi bilangan bulat non-negatif.
Inti soal ini adalah mencari apakah pada array berukuran N, terdapat subhimpunan tidak
kosong yang jumlahan elemen-elemennya habis dibagi N.
Mari kita coba mengerjakan versi lebih mudah dari soal ini: bagaimana jika yang diminta
subbarisan, bukan subhimpunan?
Anggap array A dimulai dari indeks 1 (one-based ). Misalkan kita memiliki fungsi:
k
sum(k) = ∑ A[i]
i=1
Untuk sum(0), sesuai definisi nilainya adalah 0.
Perhatikan bahwa kita dapat mendefinisikan jumlahan dari subbarisan A[`..r] menggunakan
sum:
r
∑ A[i] = sum(r) − sum(` − 1).
i=`
Jika subbarisan A[`..r] habis dibagi N, maka (sum(r) − sum(` − 1)) mod N = 0. Kita dapat
menuliskan ini dengan sum(r) mod N = sum(` − 1) mod N.
Observasi 1: Ada N kemungkinan nilai (sum(x) mod N), yaitu [0..N − 1].
Observasi 2: Ada N + 1 nilai x untuk (sum(x) mod N), yaitu untuk x ∈ [0..N].
Ingat bahwa sum(0) ada agar jumlahan subbarisan A[1..k] untuk tiap k dapat kita nyatakan
dalam bentuk: (sum(k) − sum(0)).
Observasi 3: Jika ada N + 1 kemungkinan nilai x dan ada N kemungkinan nilai sum(x) mod N,
maka pasti ada a dan b, sehingga sum(b) mod N = sum(a) mod N.
Subbarisan yang menjadi solusi adalah A[a + 1..b]. Dengan observasi ini, kita menyelesaikan
versi mudah dari soal awal kita.
16