Pembahasan OSN-P 2022 (Informatika)

Written by: 

• Leonardo Dahendra (Drakozs)

• Christoffer Edbert Karuniawan (Chrisedyong)

Reviewed by: 

• Jiriki Joeng (kizu)

*warna berdasarkan max rating Codeforces per Jul 2025

Akses soalnya di: https://osn.toki.id/data/OSNP2022.pdf 

Bagian A: Analitika & Logika 

A1. 1066

Untuk soal ini tidak ada cara pasti yang bisa dilakukan dengan cepat. Soal ini merupakan soal knapsack yang perlu dikerjakan dengan mencoba semua kemungkinan. Hal ini bisa dipercepat dengan menggunakan Dynamic Programming namun untuk soal ini, kita hanya bisa coba-coba semua kemungkinan untuk mendapatkan jawaban optimal. Jika ingin mencoba setiap kemungkinan yang ada, kita bisa coba setiap buah mulai dari buah apel, untuk buah apel kita punya 4 kemungkinan, yaitu membeli 0, 1, 2, atau 3 apel. Dari 4 kemungkinan ini, kita pasti akan mempunyai sisa uang yang berbeda-beda, kita bisa coba lanjut saja ke buah jeruk dengan sisa uang dari setiap kemungkinan, lalu ulangi hal yang sama, mencoba membeli 0, 1, 2, atau 3 jeruk. Ulangi ini untuk setiap kemungkinan yang ada, selama uang yang tersisa masih cukup, kemudian ambil pilihan yang memberikan kalori terbanyak.

Namun, jika kita tidak bisa membuat kodingan untuk soal ini dan tidak ingin mencoba semua kemungkinan yang ada, kita bisa mencoba greedy kemudian optimisasi secara manual. Dengan cara greedy, yaitu mengambil buah dengan rasio harga/kalori terbaik terlebih dahulu, kita pastinya akan mendapatkan jawaban yang mendekati optimal, namun jika masih terdapat sisa uang, kita coba ubah-ubah sedikit jawaban kita untuk mencari jawaban optimalnya. Disini rasio harga/kalori tiap buah yaitu

Apel: 2360 / 91 = 25,93

Jeruk: 2120 / 71 = 29,86

Pisang: 1890  / 105 = 18,00

Kiwi: 3770 / 103 = 36,60

Mangga: 2870 / 96 = 29,90

Karena kita ingin memaksimalkan kalori, kita akan mencoba mengambil dari rasio harga/kalori paling rendah terlebih dahulu

Sisa Uang = 25000, Jumlah Kalori = 0

Ambil 5 pisang

Sisa Uang = 15500, Jumlah Kalori = 525

Ambil 3 Apel

Sisa Uang = 8420, Jumlah Kalori = 798

Ambil 3 Jeruk

Sisa Uang = 2060, Jumlah Kalori = 1011

Dengan strategi greedy, kita akan mendapatkan jawaban yaitu 1011, namun perhatikan bahwa meskipun sisa uang kita tidak cukup untuk membeli buah apapun, sisa uangnya masih lumayan banyak, jika kita menghilangkan beberapa pilihan buah yang harganya lebih murah, kita akan bisa membeli buah lain yang harganya lebih mahal, contohnya seperti membeli mangga. Jika kita menghilangkan 1 apel dan 2 jeruk dari pilihan kita, kita akan mempunyai sisa uang 8660 dan jumlah kalori 778, dengan uang 8660, kita punya cukup uang untuk membeli 3 mangga, yang meskipun rasionya lebih jelek, setiap mangga memberikan kalori yang lebih banyak dibandingkan dengan 1 apel dan 2 jeruk. Dengan mengganti pilihan kita menjadi 3 mangga, kita akan tersisa dengan uang 50 dan jumlah kalori 1066, yang merupakan jawaban optimal dari soal ini.

A2. 4

Untuk soal ini kita bisa coba saja semua kemungkinan pasangan berbeda, karena terdapat 5 diplomat, dan setiap pasangan terdiri atas 2 diplomat, akan terdapat C(5, 2) = 10 pasangan berbeda yang mungkin yaitu (Kwak, Kwik), (Kwak, Kwuk), (Kwak, Kwek), (Kwak, Kwok), (Kwik, Kwuk), (Kwik, Kwek), (Kwik, Kwok), (Kwuk, Kwek), (Kwuk, Kwok), dan (Kwek, Kwok). 

Karena kita ditanyakan jumlah pasangan yang memerlukan penerjemah dalam berkomunikasi, berarti kita tinggal mencari pasangan dimana tidak terdapat bahasa yang sama antara kedua diplomat. Dari 10 pasangan ini, terdapat 4 pasangan yang tidak mempunyai kesamaan pasangan yaitu (Kwak, Kwik), (Kwik, Kwuk), (Kwuk, Kwek), dan (Kwek, Kwok).

A3. OA

Perhatikan bahwa huruf pada string akan mengulang kembali dari awal setiap kali kita sudah sampai diujung string. Contohnya untuk huruf pertama yaitu I, huruf ke 10 yaitu C, dan setelah itu pada huruf ke 11, akan ulang lagi dengan nilai yang sama dengan huruf pertama yaitu I. Karena mengulang setiap kali kita sudah selesai melewati setiap huruf pada string, berarti akan mengulang setiap panjang dari string, yaitu 10.

Ini dapat kita tulis kembali menjadi huruf sekarang = urutan sekarang % 10. Sebagai contoh, jika ditanya huruf pada urutan ke 203, kita bisa langsung mencarinya dengan 203 % 10 = 3, jadi huruf ke urutan ke 203 yaitu F. Rumus urutan % 10 ini sama saja maksudnya dengan mencari digit terakhir pada sebuah angka, atau digit satuannya, dimana untuk mencari digit terakhir pada 2^2022 dan 3^2023, kita bisa cek saja pola pada digit satuannya, pada angka 2 polanya yaitu

2^1 = 2

2^2 = 4

2^3 = 8

2^4 = 6(kita hanya melihat digit satuan jadi untuk angka lain bisa dibuang)

2^5 = 2

Perhatikan bahwa pola digit satuannya akan mengulang setiap 4 kali, yang berarti untuk mencari digit terakhir dari 2^2022, kita bisa tinggal cek nilai dari 2022 % 4 yaitu 2, jadi 2^2022 itu sama saja dengan 2^2 yaitu 4, dan angka pada urutan ke 4 adalah O

Untuk 3^2023 dapat kita lakukan dengan cara yang sama

3^1 = 3

3^2 = 9

3^3 = 7

3^4 = 1

3^5 = 3

Sama juga, berulang setiap 4 kali. 2023 % 4 = 3, 3^3 = 7, jadi hurufnya berada pada urutan ke 7 yaitu huruf A. Jika digabungkan akan didapatkan string OA

A4. 10

Jika kita mencoba mengerjakan dari A, dimana A bisa pergi ke B ataupun ke D akan bisa sangat panjang dan membingungkan. Karena itu, kita bisa mencoba mengerjakan dari belakang, dimulai dari H dulu. Jika kita berada di H, hanya ada 1 cara untuk ke H, yaitu dengan tidak melakukan apa-apa karena kita sudah di H. Setelah itu dari F dan G, jika kita berada di F, kita hanya bisa ke H saja, begitu juga dengan jika kita di G, jadi untuk F dan G masing-masing hanya terdapat 1 cara. Selanjutnya untuk D juga akan sama saja, D hanya bisa pergi ke F saja, dimana F hanya punya 1 cara untuk ke H, jadi untuk D juga hanya mempunyai 1 cara untuk ke H.

Untuk kandang berikutnya yaitu E, disini E bisa pergi ke 4 kandang berbeda, dimana setiap kandang masing-masing mempunyai 1 cara untuk ke H, jadi jika kita berada di kandang E, terdapat 4 cara untuk ke H. Untuk kandang C, dari situ kita bisa menuju ke E dan F, dimana E bisa ke H melalui 4 cara, dan F bisa ke H dengan 1 cara saja, jadi untuk C sendiri terdapat 5 cara untuk ke H. Untuk B kita bisa tambahkan saja E dan C, yaitu 4 +5 = 9. Terakhir untuk A, dari A kita bisa ke B dan D, jadi total terdapat 9 + 1 = 10 cara untuk menuju ke H dari A. 

Disini kita mengerjakan dari belakang agar tidak perlu menghitung berulang-ulang, seperti contohnya pada kandang B dan C yang keduanya bisa ke kandang E, jika kita tidak menyimpan bahwa dari kandang E, terdapat 4 cara untuk ke kandang H, maka kita akan perlu menghitung ulang kembali dari B dan C, teknik ini juga disebut Dynamic Programming.

A5.  60

Dari soal yang diberikan, urutan yang sudah pasti hanya urutan untuk N, dimana untuk urutan yang lainnya harus kita coba untuk mengetahui jumlah kemungkinannya. Untuk pilihan yang bisa kita coba terdapat beberapa, kita bisa mencoba mulai dari H, atau GF, atau J__M/M__J. Disini mencoba dari urutan manapun tetap bisa, namun agar tidak terlalu panjang, kita akan coba dari J__M, karena opsi ini mempunyai jumlah posisi berbeda yang paling sedikit. Untuk semua kasus yang mungkin yaitu

NJ__M___

N_J__M__

N__J__M_

N___J__M

Untuk posisi M__J, kita bisa kali 2 saja jawaban yang didapatkan

Kasus 1: 

NJ__M___

Setelah itu, kita bisa coba semua kemungkinan GF

NJGFM___ = 0(H harus sebelum F)

NJ__MGF_ = 2(posisi H yang mungkin) * 2(banyak cara memasukkan K dan L ke 2 tempat tersisa) = 4

NJ__M_GF = 3 * 2 = 6

Kasus 2: 

N_J__M__

Coba GF

N_JGFM__ = 1 * 2 = 2

N_J__MGF = 3 * 2 = 6

Kasus 3:

N__J__M_

Coba GF

NGFJ__M_ = 0

N__JGFM_ = 2 * 2 = 4

Kasus 4:

N___J__M

Coba GF

NGF_J__M = 0

N_GFJ__M = 1 * 2 = 2

N___JGFM = 3 * 2 = 6

Total semua kasus = 6 + 4 + 2 + 6 + 4 + 2 + 6 = 30

Karena bentuk J__M juga bisa diubah menjadi M__J, jawaban kita perlu dikali 2

Jawaban akhir = 30 * 2 = 60

A6. 143

Karena keliling dari lahan wajib 100 meter. Untuk panjang dan lebar dari lahan sendiri berarti totalnya harus  50 m yang didapatkan dari rumus 2 * p + 2 * l = 100, p + l = 50. Untuk memasang tiang-tiang tersebut, mungkin awalnya kita akan berpikir untuk memasang setiap tiang secara berurutan lurus horizontal dan vertikal, dengan tiang pertama di pojok kiri atas dengan jarak 2 meter dari dinding, kemudian setelah itu, tiang berikutnya akan berada 2 m di kanan, dan 2 m di bawah, dilanjutkan terus sampai didapatkan jumlah maksimal. 

Jika menggunakan cara tersebut, kita akan mendapatkan rumus ⌊(p - 2) / 2⌋ * ⌊(l - 2) / 2⌋. Rumus ini bisa didapatkan dengan melihat polanya saja, untuk lebar lahan, jika lebarnya 2, kita tidak bisa memasang tiang sama sekali, jika lebarnya 4, kita hanya bisa memasang 1 tiang ditengah, jika 6 bisa memasang 2, dst, sama juga dengan lebar. Untuk memaksimalkan hasilnya, kita bisa pilih p = 26 dan l = 24 atau sebaliknya, yang akan didapatkan hasil yaitu 

= ⌊(26 - 2) / 2⌋ * ⌊(24 - 2) / 2⌋

= ⌊24 / 2⌋ * ⌊22 / 2⌋

= 12 * 11

= 132

Meskipun jawaban ini terlihat sudah benar, perhatikan bahwa sebenarnya ada cara lain yang lebih efektif untuk memasang tiang-tiang tersebut, daripada kita memasang tiang seperti berikut

Kita bisa memasang tiang-tiang tersebut seperti ini

Disini warna kuning menandakan posisi sebelumnya, dan warna hijau menandakan posisi baru. Pada posisi baru ini, kita dapat menggunakan lahan yang lebih sedikit untuk memasang jumlah tiang yang sama dan jarak antar setiap tiang akan tepat 2 m. Tiang-tiang ini dapat kita representasikan sebagai sebuah lingkaran dengan jari-jari 1 m, dimana titik tengah lingkaran merupakan tiang-tiang kita, dengan representasi tersebut, gambar tadi akan terlihat seperti ini

Karena jarak antara tiang dan tembok masih wajib 2 m, kita bisa kurangi saja panjang dan lebar sebanyak 1 m pada setiap ujung agar jarak antara tiang dan tembok akan tetap 2 m meskipun jari-jarinya hanya 1 m. Dengan cara ini, sekarang pertanyaannya berubah menjadi berapa banyak lingkaran dengan jari-jari 1 m yang bisa kita masukkan kedalam sebuah persegi panjang dengan ukuran (p - 2) * (l - 2).

Untuk mengetahui jarak vertikal antara lingkaran atas dengan yang dibawahnya, kita bisa menggunakan rumus pythagoras yaitu 2^2 = a^2 + b^2, disini a merepresentasikan jarak vertikal dan b merepresentasikan jarak horizontal. Perhatikan bahwa lingkaran dibawah akan berada tepat diantara 2 lingkaran, yang berarti jarak horizontal dari lingkaran atas dan bawah sama dengan jari-jari lingkaran

4 = a^2 + 1^2

a^2 = 3

a = sqrt(3)

Jadi jarak vertikal antara lingkaran atas dan lingkaran bawah adalah akar 3. Anggap panjang baru sebagai pB dan lebar baru sebagai lB, nilai keduanya yaitu pB = p - 2, lB = l - 2. Untuk menghitung jumlah lingkaran yang mungkin, kita bisa bagi menjadi 2 kasus, yaitu untuk barisan ganjil dan barisan genap.

Jumlah baris(b) = ⌊(pB - 2) / sqrt(3)⌋ + 1

Jumlah baris ganjil(bA) = ⌈b / 2⌉

Jumlah baris genap(bE) = ⌊b / 2⌋

Jumlah lingkaran di baris ganjil(lA) = ⌊lB / 2⌋

Jumlah lingkaran di baris genap(lE) = ⌊(lB - 1) / 2⌋

Total lingkaran = bA * lA + bE * lE

Untuk mencari nilai p dan l sendiri kita bisa coba-coba, nanti akan ditemukan jawaban optimal pada p = 25 dan l = 25 dimana akan didapatkan nilai pB = 23 dan lB = 23

Jumlah baris(b) = ⌊(23- 2) / sqrt(3)⌋ + 1

= ⌊21 / sqrt(3)⌋ + 1

= 12 + 1

= 13

Jumlah baris ganjil(bA) = ⌈b / 2⌉

= ⌈13 / 2⌉

= 7

Jumlah baris genap(bE) = ⌊b / 2⌋

= ⌊13 / 2⌋

= 6

Jumlah lingkaran di baris ganjil(lA) = ⌊lB / 2⌋

= ⌊23 / 2⌋

= 11

Jumlah lingkaran di baris genap(lE) = ⌊(lB - 1) / 2⌋

= ⌊(23 - 1) / 2⌋

= ⌊22 / 2⌋

= 11

Total lingkaran = bA * lA + bE * lE

= 7 * 11 + 6 * 11

= 77 + 66

= 143

Dimana visualisasi jawaban akhirnya sendiri akan terlihat seperti berikut

A7. 300

Untuk mempermudah perhitungan, daripada kita langsung menghitung berapa kemungkinan yang memenuhi syarat, kita bisa ubah menjadi berapa total kemungkinan dikurang jumlah kemungkinan yang tidak memenuhi syarat. Cara ini akan mendapatkan hasil yang sama persis dan akan jauh lebih mudah untuk dihitung. Pertama untuk menghitung total kemungkinan, kita perlu memilih 3 bebek jantan dari 6 bebek jantan, kemudian 3 bebek betina dari 6 bebek betina, dan akhirnya mereka akan digabung menjadi sebuah tim. Untuk mencari kemungkinannya, berarti kita pakai kombinasi 3 dari 6 untuk memilih 3 bebek dari 6 bebek yang ada

C(6, 3) = 6!/(3!(6-3)!) = 20

Untuk setiap pemilihan 3 jantan dapat digabungkan dengan pemilihan 3 betina manapun untuk membentuk sebuah tim, berarti kita akan mengalikan keduanya untuk mendapatkan semua kemungkinan

C(6, 3) * C(6, 3)

= 20 * 20

= 400

Terdapat 400 cara untuk membentuk sebuah tim.

Agar sebuah tim disebut tidak valid, ketika memilih 3 jantan, salah satunya harus merupakan jantan dengan berat paling ringan, begitu juga dengan ketika memilih 3 betina, salah satunya harus merupakan betina dengan berat paling ringan. Dengan kata lain, dari 3 slot yang ada, 1 nya sudah pasti ditempati oleh jantan/betina yang paling ringan, jadi kita hanya perlu memilih 2 bebek lagi dari 5 bebek yang ada.

C(5, 2) = 5!/(2!(5-2)!) = 10

Total kemungkinan jumlah tim yang tidak valid

C(5, 2) * C(5, 2)

= 10 * 10

= 100

Jumlah kemungkinan membentuk tim yang valid

= Total kemungkinan - jumlah kemungkinan yang tidak valid

= 400 - 100

= 300

A8. 70000

Anggap harga tiket pada baris ketiga sebagai x, karena diketahui selisih harga pada 2 baris yang berdekatan adalah 10000 dan baris pertama merupakan baris paling mahal, akan diketahui harga tiket tiap baris yaitu

baris 1 = x + 20000

baris 2 = x + 10000

baris 3 = x

baris 4 = x - 10000

baris 5 = x - 20000

baris 6 = x - 30000

Karena diperlukan pemasukan tepat 22500000, maka total harga dari setiap baris wajib sama persis, yang akan didapatkan rumus yaitu

25(x + 20000) + 35(x + 10000) + 50x + 70(x - 10000) + 95(x - 20000) + 125(x - 30000) = 22500000

25x + 500000 + 35x + 350000 + 50x + 70x - 700000 + 95x - 1900000 + 125x - 3750000 = 22500000

400x - 5500000 = 22500000

400x = 28000000

x = 70000

A9. 342

Perhatikan bahwa kita tidak bisa langsung menggunakan rumus seperti 100 - 3x / 3 + 5x / 7 = 0, dengan x merupakan jumlah hari, untuk mendapatkan jawaban. Hal ini dikarenakan rumus tersebut akan melihat nilai fraksional, dimana pada hari pertama kita dianggap memakan 1 permen dan mendapatkan 0,7 permen yang tidak sesuai dengan permintaan soal. Agar tetap sesuai dengan permintaan soal, kita bisa menghitung harinya setiap kelipatan 21, yaitu KPK dari 3 dan 7, agar tetap sesuai permintaan soal, kita perlu memproses memakan permennya setiap 3 hari sekali, begitu juga dengan mendapatkan permen yang harus kita proses setiap 7 hari sekali, agar dapat memproses keduanya bersamaan, kita menggunakan KPK dari 3 dan 7 yaitu  21.

Setiap 21 hari, kita akan memakan 3 * (21 / 3) = 21 permen dan mendapatkan 5 *(21 / 7) = 15 permen, atau dengan kata lain, jumlah permen kita akan berkurang 6 setiap 21 hari. Kita sekarang cari proses ini harus diulang berapa kali sampai permen kita hampir habis, karena terdapat 100 permen diawal, kita paling banyak bisa melakukan proses ini sebanyak 100 / 6 = 16 kali, jika kita melakukannya 17 kali akan berlebihan dan melewati jawaban yang kita perlukan. 

Setelah 16 kali, kita akan tersisa 100 - 16 * 6 = 4 permen dan berada di hari ke 16 * 21 = 336. Setelah ini kita dapat simulasikan saja sampai permen kita habis, pada hari ke 339, kita akan memakan 3 permen lagi, jadi kita tersisa 1 permen, dan pada hari ke 342, kita akan memakan sisa permen terakhir kita. Perhatikan bahwa karena kita akan mendapatkan 5 permen setiap 7 hari, kita hanya akan mendapatkan tambahan permen pada hari ke 343. Disini karena permen sudah habis di hari ke 342, maka kita sudah mendapatkan jawaban kita.

Studi Kasus B1: Lampu Hias

B1.1. YA

Lampu pertama akan menyala pada detik ke 4, 8, 12, 16, ...

Lampu kedua akan menyala pada detik ke 10, 20, 30, 40, ...

Lampu ketiga akan menyala pada detik ke 12, 24, 36, 48, ....

Lampu akan menyala jika waktu saat ini merupakan kelipatan dari rentang waktunya, dengan kata lain, lampu akan menyala jika waktu % rentang waktu == 0.

Lampu pertama = 3000 % 4 = 0

Lampu kedua = 3000 % 10 = 0

Lampu ketiga = 3000 % 12 = 0

Karena pada detik ke 3000 nilai modulo ketiga lampu adalah 0, maka ketiga lampu akan menyala bersamaan pada detik ke 3000

B1.2. 6

Untuk soal ini kita bisa coba saja kemungkinan yang ada karena angkanya sangat kecil

1, 2, 3, 4, 5, 6, ....

2, 4, 6, ...

3, 6, ....

Dapat dilihat bahwa ketiganya akan menyala bersamaan ketika waktu = 6

B1.3. 36

Perhatikan bahwa agar ketiga lampu menyala, maka lampu harus merupakan kelipatan dari rentang waktu ketiga lampu, atau dengan kata lain, waktu harus merupakan KPK dari rentang waktu ketiga lampu. 

Untuk mencari KPK dari 3 angka, terdapat beberapa cara yang dapat digunakan, salah satunya yaitu dengan faktor prima

4 = 2^2

6 = 2^1 * 3^1

9 =            3^2

Untuk mencari KPKnya, kita ambil saja nilai terbesar pada setiap prima yaitu 2^2 dan 3^2, dimana kita akan mendapatkan nilai 

= 2^2 * 3^2

= 4 * 9

= 36

Ketiga lampu akan menyala setiap 36 detik, dan pertama kali menyala bersama ketika waktu = 36

Soal Pemrograman Subsoal 1

Cek saja apakah T habis dibagi P, Q, dan R

Kompleksitas: O(N)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {

  int P, Q, R;

  cin >> P >> Q >> R;

  int N;

  cin >> N;

  for (int i = 0; i < N; i++) {

      int T;

      cin >> T;

      if (T % P == 0 && T % Q == 0 && T % R == 0) cout << "YA\n";

      else cout << "TIDAK\n";

  }

  return 0;

}

Soal Pemrograman Subsoal 2

Cek saja apakah T habis dibagi P, Q, dan R. Namun menggunakan tipe data long long agar tidak overflow

Kompleksitas: O(N)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {

   ll P, Q, R;

   cin >> P >> Q >> R;

   int N;

   cin >> N;

   for (int i = 0; i < N; i++) {

       ll T;

       cin >> T;

       if (T % P == 0 && T % Q == 0 && T % R == 0) cout << "YA\n";

       else cout << "TIDAK\n";

   }

   return 0;

}

Studi Kasus B2. Mengangkut Bebek

B2.1. 35

Karena hanya terdapat 1 kandang, kita hanya bisa memasukkan semua bebek kedalam kandang tersebut, jadi biaya pengangkutannya adalah 5 * (2 + 2 + 3) = 5 * 7 = 35

B2.2. 100

Disini karena berat semua bebek sama, kita dapat memilih untuk memasukkan bebek manapun ke dalam kandang yang kita pilih. Namun, untuk kandangnya sendiri, pasti akan lebih untung jika kita menggunakan kandang dengan biaya angkut yang lebih rendah, dan setelah kandang tersebut penuh, baru kita lanjutkan ke kandang berikutnya dengan biaya angka termurah.

Dengan cara ini, kita akan memasukkan 3 bebek ke kandang 2, 3 bebek ke kandang 3, dan 1 bebek terakhir ke kandang 1. Biaya yang perlu dibayar yaitu

=  2 * (5 + 5 + 5) + 3 * (5 + 5 + 5) + 5 * (5) 

= 2 * 15 + 3 * 15 + 5 * 5

= 30 + 45 + 25

= 100

B2.3. 59

Perhatikan bahwa biaya angkut kita pasti akan lebih minimum jika kita memasukkan bebek dengan berat terbesar kedalam kandang dengan biaya angkut terkecil. Dengan observasi ini, kita bisa memasukkan 3 bebek paling berat ke dalam kandang 2, kemudian sisa 6 bebeknya kita masukkan kedalam kandang 1.

Biaya = 1 * (8 + 7 + 6) + 2 * (5 + 4 + 3 + 3 + 2 + 2)

= 1 * 21 + 2 * 19

= 21 + 38

= 59

Soal Pemrograman Subsoal 1

Utamakan kandang yang paling murah ke kandang yang paling mahal. Karena berat bebek sama tidak akan jadi masalah

Kompleksitas: O(K log K)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {

   int K;

   cin >> K;

   vector<int> P(K), C(K);

   for (auto &i : P) cin >> i;

   for (auto &i : C) cin >> i;

   int N;

   cin >> N;

   int B;

   for (int i = 0; i < N; i++) cin >> B;

   vector<int> p(K);

   iota(p.begin(), p.end(), 0);

   sort(p.begin(), p.end(), [&](const int &i, const int &j) {

       return C[i] < C[j];

   });

   ll ans = 0;

   for (int i = 0, j = 0; i < N; i++) {

       while (P[p[j]] == 0) j++;

       P[p[j]]--;

       ans += 1LL * C[p[j]] * B;

   }

   cout << ans << '\n';

   return 0;

}

Soal Pemrograman Subsoal 2

Lakukan pengurutan untuk kandang yang paling murah ke kandang yang paling mahal serta berat bebek yang paling besar ke berat bebek yang paling kecil. Dengan greedy ini dijamin akan selalu optimal karena berat bebek yang besar akan dimasukkan ke kandang yang biayanya murah.

Kompleksitas: O(K log K + N log N)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {

   int K;

   cin >> K;

   vector<int> P(K), C(K);

   for (auto &i : P) cin >> i;

   for (auto &i : C) cin >> i;

   int N;

   cin >> N;

   vector<int> B(N);

   for (auto &i : B) cin >> i;

   sort(B.begin(), B.end(), greater<int>());

   vector<int> p(K);

   iota(p.begin(), p.end(), 0);

   sort(p.begin(), p.end(), [&](const int &i, const int &j) {

       return C[i] < C[j];

   });

   ll ans = 0;

   for (int i = 0, j = 0; i < N; i++) {

       while (P[p[j]] == 0) j++;

       P[p[j]]--;

       ans += 1LL * C[p[j]] * B[i];

   }

   cout << ans << '\n';

   return 0;

}

Studi Kasus B3. Dewan Perwakilan Bebek

B3.1. 4

Nilai tingkat perpecahan didapatkan dari selisih ego tertinggi dan terendah dari kandidat yang terpilih, jika kandidat yang terpilih mempunyai ego 7, 4, dan 8 maka tingkat perpecahannya yaitu 8 - 4 = 4

B3.2. 3

Perhatikan bahwa pasti akan lebih optimal untuk kita memilih bebek-bebek yang nilai egonya berurutan untuk meminimalkan tingkat perpecahan. Untuk tingkat ego dari kelima bebek jika diurutkan akan menjadi 1, 4, 7, 8, 10. Contohnya jika kita diminta memilih 3 bebek, dan kita memilih 1, 4, 8, pasti akan lebih optimal jika kita mengubah 8 menjadi 7 agar tingkat perpecahan lebih minimum, atau bisa juga kita mengganti 1 menjadi 7. 

Dengan observasi ini, kita bisa coba saja 3 bebek berurutan dan hitung tingkat perpecahannya

1, 4, 7 = 7 - 1 = 6

4, 7, 8 = 8 - 4 = 4

7, 8, 10 = 10 - 7 = 3

Didapatkan bahwa tingkat perpecahan minimal yang bisa dicapai adalah 3

B3.3. 4

Dari solusi sebelumnya, kita tahu bahwa kita bisa memilih 3 anggota sebagai dewan perwakilan bebek dengan tingkat perpecahan 3. Jika tingkat perpecahan maksimum yang boleh adalah 7, maka kita sisa mengecek apakah terdapat kemungkinan jawabannya adalah 4 ataupun 5. 

Jika kita mencoba memilih 5 bebek untuk menjadi anggota dewan perwakilan, maka kita wajib memilih semua bebek yang ada, dimana tingkat perpecahannya akan menjadi 10 - 1 = 9 yang melebihi 7. Maka tidak mungkin untuk membentuk dewan perwakilan dengan 5 bebek, selanjutnya kita cek apakah mungkin untuk membentuk dewan perwakilan dengan 4 bebek dengan cara yang sama dengan soal sebelumnya.

1, 4, 7, 8 = 8 - 1 = 7

4, 7, 8, 10 = 10 - 4 = 6

Disini dapat dilihat bahwa kita bisa membuat dewan perwakilan dengan 4 bebek, untuk bebek yang kita pilih sendiri terdapat beberapa kemungkinan.

Soal Pemrograman Subsoal 1

Gunakan two pointers yaitu hitung apabila bebek terkiri yang kita ambil sedemikian sehingga bebek terkanan yang kita ambil optimalnya dimana. Jawaban kita maksimumkan jika bebek query ada di antara bebek terkiri dan terkanan.

Kompleksitas: O(N log N)

#include <bits/stdc++.h>

using namespace std;

int main() {

   int n, p, q;

   cin >> n >> p >> q;

   assert(q == 1);

   vector<int> E(n);

   for (int i = 0; i < n ;i++) {

       cin >> E[i];

   }

   int x;

   cin >> x;

   --x;

   int bx = E[x];

   sort(E.begin(), E.end());

   int l = 0, ans = 1;

   for (int r = 0; r < n; r++) {

       while (E[r] - E[l] > p) l++;

       if (E[l] <= bx && bx <= E[r]) {

           ans = max(ans, r - l + 1);

       }

   }

   cout << ans << '\n';

   return 0;

}

Soal Pemrograman Subsoal 2

Lakukan precompute untuk setiap bebek yang mungkin sehingga untuk setiap query kita bisa jawab dengan O(1). Untuk melakukan precompute bisa menggunakan two pointers dan priority queue.

Kompleksitas: O(N log N + Q)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {

   int N, P, Q;

   cin >> N >> P >> Q;

   vector<int> E(N);

   for (auto &i : E) cin >> i;

   vector<int> p(N);

   iota(p.begin(), p.end(), 0);

   sort(p.begin(), p.end(), [&](const int &i, const int &j) {

       return E[i] < E[j];

   });

   vector<int> ans(N);

   priority_queue<pair<int,int>> pyqe;

   for (int i = 0, j = 0; i < N; i++) {

       while (j + 1 < N && E[p[j + 1]] - E[p[i]] <= P) j++;

       pyqe.push({j - i + 1, j});

       while (!pyqe.empty() && pyqe.top().second < i) pyqe.pop();

       ans[p[i]] = pyqe.top().first;

   }

   for (int i = 0; i < Q; i++) {

       int X;

       cin >> X;

       cout << ans[X - 1] << '\n';

   }

   return 0;

}

Studi Kasus B4. Memasang Karpet

B4.2. 162

Pada soal ini, kita tidak bisa menghitung untuk setiap kotaknya lagi, karena karpet jenis kedua yang bisa memanjang hingga ke kotak berikutnya. Namun untungnya, karpet jenis kedua hanya bisa memanjang ke 1 kotak berikutnya saja, dan ketika memanjang hanya bisa mengambil antara diagonal dengan bentuk / atau diagonal dengan bentuk \. 

Untuk mengerjakan soal ini kita bisa menggunakan DP, dimana DP kita akan mempunyai 3 variasi, yaitu ketika sebuah kotak masih kosong(diberi nilai 0), kotak terisi dengan diagonal bentuk /(diberi nilai 1), dan kotak terisi dengan diagonal bentuk \(diberi nilai 2). Kita bisa kerjakan dari M = 1 agar lebih mudah.

Ketika M = 1

DP[1][2] = 1(jika diagonal / sudah terisi, maka 1 bagian kosong lainnya wajib diisi dengan karpet jenis 1 yang tersisa)

DP[1][1] = 1

DP[1][0] = 2(jika kotak dengan panjang 1 masih kosong, kita hanya bisa menggunakan karpet jenis 1, dan ada 2 cara seperti pada soal sebelumnya)

Ketika M = 2

DP[2][2] = DP[1][0](menggunakan karpet jenis 1 untuk menutupi lubang pada kotak ini) + DP[1][1](menggunakan karpet jenis 2 untuk menutupi lubang pada kotak ini, yang sekaligus menutupi sebagian lubang pada kotak berikutnya)

DP[2][2] = 2 + 1 = 3

DP[2][1] = DP[1][0] + DP[1][2]

DP[2][1] = 2 + 1 = 3

DP[2][0] = DP[2][1](Menggunakan karpet jenis 1 yang bentuknya /) + DP[2][2](Menggunakan karpet jenis 1 yang bentuknya \)

DP[2][0] = 3 + 3 = 6

Untuk ketika kotak kosong, kita tidak perlu mencoba menggunakan karpet jenis 2 karena sudah ditangani pada DP[2][1] dan DP[2][2], jika kita mencoba menggunakan karpet jenis 2, maka akan terdapat petak kosong yang wajib diisi dengan karpet jenis 1, yang pada akhirnya bentuknya akan sama dengan DP[2][1] atau DP[2][2].

Ketika M = 3

DP[3][2] = DP[2][0] + DP[2][1] = 6 + 3 = 9

DP[3][1] = DP[2][0] + DP[2][2] = 6 + 3 = 9

DP[3][0] = DP[3][1] + DP[3][2] = 9 + 9 = 18

Ketika M = 4

DP[4][2] = DP[3][0] + DP[3][1] = 18 + 9 = 27

DP[4][1] = DP[3][0] + DP[3][2] = 18 + 9 = 27

DP[4][0] = DP[4][1] + DP[4][2] = 27 + 27 = 54

Ketika M = 5

DP[5][2] = DP[4][0] + DP[4][1] = 54 + 27= 81

DP[5][1] = DP[4][0] + DP[4][2] = 54 + 27= 81

DP[5][0] = DP[5][1] + DP[5][2] = 81 + 81 = 162

Untuk DP nya bisa disederhanakan menjadi 2 variasi saja, ketika kotak masih kosong dan ketika kotak tidak kosong karena untuk bentuk diagonal \ maupun / akan mempunyai nilai yang sama.

Soal Pemrograman Subsoal 1

Bisa menggunakan pendekatan Dynamic Programming untuk menghitung. Definisi Dynamic Programming yang ada adalah DP[M][0] = banyak cara untuk mengisi kotak 1 x M secara penuh. DP[M][1] = banyak cara untuk mengisi kotak 1 x M namun untuk kotak ke M tidak penuh. Transisi bisa kita lihat yaitu

DP[i][1] = DP[i - 1][0] + DP[i - 1][1]

DP[i][0] = DP[i][1] + DP[i][1]

Dengan base case merupakan DP[0][0] = 1

Jawaban kita ada di DP[M][0]

Kompleksitas: O(M)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

constexpr int mod = 1'000'000'007;

int N, M;

int dp[100'000][5];

inline int add(int a, int b) {

  a += b;

  if (a >= mod) a -= mod;

  return a;

}

inline int mul(int a, int b) {

  return 1LL * a * b % mod;

}

int main() {

  cin >> N >> M;

   dp[0][0] = 1;

   for (int i = 1; i <= M; i++) {

       dp[i][1] = add(dp[i - 1][0], dp[i - 1][1]);

       dp[i][0] = add(dp[i][1], dp[i][1]);

   }

   cout << dp[M][0] << '\n';

  return 0;

}

Studi Kasus B5. Melompati Lapangan

B5.1. TIDAK

Perhatikan bahwa dari suatu posisi (i, j) kita hanya bisa melompat ke posisi dimana i' >= i dan j' >= j, dengan kata lain kita hanya bisa melompat ke arah kanan bawah, jadi kita tidak bisa keatas maupun ke kiri.

B5.2. TIDAK

Pada petak (1,2), Pak Dengklek hanya bisa melompat ke petak (1,3), (2, 2), atau (2, 3) dimana pada ketika petak ini, kita tidak bisa kemana-mana lagi karena ketiga petak ini mempunyai nilai 0.

B5.3. 14

Untuk mendapatkan jawaban berapa banyak cara untuk bergerak ke (3, 4) dari suatu petak tertentu, kita perlu menjumlahkan berapa banyak cara untuk bergerak ke (3, 4) dari semua petak yang bisa dituju oleh petak tersebut. Ini merupakan soal DP yang akan jauh lebih mudah jika kita kerjakan dari belakang

DP[3][4] = 1(jika sudah di 3,4 berarti tidak bisa kemana-mana dan jawabannya diterima)

DP[2][4] = 1

DP[1][4] = 2(Dari posisi 1,4 kita bisa melompat ke 2,4 atau 3,4 jadi kita ambil nilai DP[2][4] + DP[3][4])

DP[3][3] = 1

DP[2][3] = 0

DP[1][3] = 0

DP[3][2] = 1

DP[2][2] = 0

DP[1][2] = 0

DP[3][1] = 3

DP[2][1] = 5

DP[1][1] = 14(kita bisa ke semua petak dari petak 1,1 jadi kita jumlahkan DP dari semua petak yang ada)

Soal Pemrograman Subsoal 1

Gunakan strategi Dynamic Programming 2 Dimensi yaitu hitung banyak cara yang mungkin untuk sampai di koordinat sekarang. Transisi dilakukan dengan iterasi kembali untuk masing-masing koordinat.

Kompleksitas: O(N^2 M^2)

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 1'000'000'007;

int N, M;

int A[2004][2004], dp[2004][2004];

int add(int x, int y) {

  x += y;

  if (x >= mod) x -= mod;

  return x;

}

int sub(int x, int y) {

  x -= y;

  if (x < 0) x += mod;

  return x;

}

int main() {

  cin >> N >> M;

  for (int i = 1; i <= N; i++) {

      for (int j = 1; j <= M; j++) {

          cin >> A[i][j];

      }

  }

  dp[1][1] = 1;

  for (int i = 1; i <= N; i++) {

      for (int j = 1; j <= M; j++) {

          for (int k = i; k <= min(N, i + A[i][j]); k++) {

              for (int l = j; l <= min(M, j + A[i][j]); l++) {

                  if (k == i && l == j) continue;

                  dp[k][l] = add(dp[k][l], dp[i][j]);

              }

          }

      }

  }

  cout << dp[N][M] << '\n';

  return 0;

}

Soal Pemrograman Subsoal 2

Untuk mempercepat, kita bisa menggunakan prefix difference Dynamic Programming 2 Dimensi

Kompleksitas: O(N M)

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 1'000'000'007;

int N, M;

int A[2004][2004], dp[2004][2004];

int add(int x, int y) {

   x += y;

   if (x >= mod) x -= mod;

   return x;

}

int sub(int x, int y) {

   x -= y;

   if (x < 0) x += mod;

   return x;

}

int main() {

   cin >> N >> M;

   for (int i = 1; i <= N; i++) {

       for (int j = 1; j <= M; j++) {

           cin >> A[i][j];

       }

   }

   dp[1][1] = 1;

   dp[1][2] = -1;

   dp[2][1] = -1;

   dp[2][2] = 1;

   for (int i = 1; i <= N; i++) {

       for (int j = 1; j <= M; j++) {

           dp[i][j] = add(dp[i][j], sub(add(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]));

           dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]);

           dp[i][j + 1] = add(dp[i][j + 1], dp[i][j]);

           dp[i + 1][j + 1] = sub(dp[i + 1][j + 1], dp[i][j]);

           int I = min(N, i + A[i][j]);

           int J = min(M, j + A[i][j]);

           dp[I + 1][j] = sub(dp[I + 1][j], dp[i][j]);

           dp[i][J + 1] = sub(dp[i][J + 1], dp[i][j]);

           dp[I + 1][J + 1] = add(dp[I + 1][J + 1], dp[i][j]);

       }

   }

   cout << dp[N][M] << '\n';

   return 0;

}