Tags

3. Bebek Istimewa

Pembuat soal: Irvan Jahja

Link:

Subsoal 1

Batasan: 1 <= N <= 3 dan 1 <= M <= 10

Setiap kali Pak Ganesh membuka sebuah kandang, terdapat N – 1 kandang yang tidak terlihat. Karena Pak Ganesh membuka kandang-kandang M kali, maka terdapat (N – 1)^M kandidat solusi. Coba semua (N – 1)^M buah kandidat solusi tersebut, dan pilih konfigurasi pemindahan yang memenuhi batasan soal (bebek selalu berpindah ke kandang yang berada tepat di sebelahnya). Jika tidak ada yang memenuhi, outputkan menyerah.

Kompleksitas waktu: O(M (N-1)^M)

Subsoal 2

Batasan: 1 <= N <= 10 dan 1 <= M <= 10

Kita definisikan rute seekor bebek sebagai perpindahan bebek istimewa dari pembukaan pertama Pak Ganesh hingga yang ke-M tanpa peduli apakah rute ini melalui kandang yang sempat dibuka atau tidak pada saat tertentu. Tentu saja terdapat tidak lebih dari 2^(M – 1) rute yang dimulai dari kandang tertentu, karena setiap saat Pak Dengklek hanya memiliki 2 pilihan untuk memindahkan bebeknya: ke kiri atau ke kanan.

Karena terdapat N kandang yang bisa menjadi kandang pertama di rute tersebut, terdapat N 2^(M – 1) kemungkinan rute. Coba semua kemungkinan, dan cari yang valid, maka kita dapatkan tebakan yang valid (sesuai konstrain soal).

Kompleksitas waktu: O(N M 2^(M – 1))

Subsoal 3

Batasan: 1 <= N <= 2000 dan 1 <= M <= 1000
Dynamic Programming.
Anggap f(t, i) bernilai true jika dan hanya jika pada pembukaan ke-t (1 <= t <= M) oleh Pak Ganesh, apakah ada konfigurasi pemindahan bebek istimewa oleh Pak Dengklek valid yang berakhir di i.

Kita dapatkan rekurens berikut:
Sebagai bagian dari definisi, kita anggap f(M + 1, i) = true untuk semua i.
Untuk t > 0:
f(t, i) = false, jika Pak Ganesh membuka kandang i pada pembukaan ke-t.
f(t, i) = f(t + 1, i – 1), untuk i = N
f(t, i) = f(t + 1, i + 1), untuk i = 1
f(t, i) = f(t + 1, i – 1) OR f(t + 1, i + 1), untuk 1 < i < N

Gunakan dynamic programming untuk menghitung f(t, i).

Jika tidak ada i sedemikian sehingga f(1, i) bernilai true, maka outputkan menyerah. Selain itu gunakan algoritma ini untuk mencetak solusi:

  1. pilih sebuah bilangan i sedhingga f(t, i) adalah true. Di mana t = 1.
  2. cetak i
  3. Jika t = M, berhenti. Selain itu, ke langkah 4.
  4. Jika i – 1 >= 1 dan f(t + 1, i – 1) adalah true, lakukan pengisian i = i – 1 dan t = t + 1, lalu ke langkah 3. Selain itu, ke langkah 5.
  5. Jika i + 1 <= N dan f(t + 1, i + 1) adalah true, lakukan pengisian i = i + 1 dan t = t + 1, lalu ke langkah 3.
Kompleksitas waktu: O(NM)

Subsoal 4

Batasan: 2000 < N <= 200000 dan 1 <= M <= 1000

Lemma 3.1 Untuk N >= 2M + 2, pasti terdapat posisi i sehingga kandang i dan i + 1 tidak pernah dibuka oleh Pak Ganesh.

Pembuktian Terdapat setidaknya N – M kandang yang tidak pernah dibuka Pak Ganesh. Nomori mereka dari 1 sampai N – M berdasarkan posisinya (kiri ke kanan). Untuk membentuk konfigurasi kandang awal, kita perlu “menyisipkan” kandang-kandang yang pernah dibuka (M kandang) di antara N – M kandang tersebut. Jika ada i sehingga antara kandang tidak pernah dibuka ke-i dan ke-(i + 1) tidak tersisip, maka lemma 3.1 benar. Perhatikan bahwa ada (N – M) – 1 tempat yang bisa disisipkan M kandang tersebut. Karena N >= 2M + 2, banyaknya tempat tersebut >= (2M + 2 – M) – 1. Yaitu lebih dari M. Karena itu, pasti terdapat tempat yang tidak tersisip oleh kandang yang pernah dibuka. Sehingga lemma 3.1 benar. QED.

Berdasarkan lemma 3.1, jika N >= 2M + 2 kita hanya perlu memilih dua kandang bersebelahan yang tidak pernah dibuka Pak Ganesh. Lalu, konfigurasi pemindahan Pak Dengklek hanya perpindahan bebek istimewa di antara kedua kandang tersebut secara bergantian terus-menerus.

Akan tetapi, jika diperhatikan secara cermat pada subsoal ini:
Untuk 1 <= M < 1000, pertidaksamaan N >= 2M + 2 pasti terpenuhi. Tetapi, untuk M = 1000, N >= 2M + 2 belum tentu terpenuhi. Yakni, pada kasus M = 1000 dan N = 2001. Untuk kasus ini, gunakan dynamic programming yang dijelaskan di subsoal 3. Jika Anda tidak memperhatikan kasus ini secara cermat, Anda tidak bisa memperoleh nilai penuh di soal ini.

Kompleksitas waktu: Untuk N = 2001 dan M = 1000, O(NM). Selain itu, O(N + M).

Advertisements