Pembahasan OSN-P 2023 (Informatika)

Written by: 

• Christoffer Edbert Karuniawan (Chrisedyong)

Reviewed by: 

• Leonardo Dahendra (Drakozs)

• Jiriki Joeng (kizu)

*warna berdasarkan max rating Codeforces per Jul 2025

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

Bagian A: Analitika & Logika 

A1. 19990

Jika d1d2d3 ketiganya sama dengan d4d5d6 maka banyaknya cara adalah 10^4 = 10000

Jika d1d2d3 ketiganya sama dengan d5d6d7 maka banyaknya cara adalah 10^4 = 10000

Jika d1d2d3 ketiganya sama dengan d4d5d6 dan d5d6d7 maka banyaknya cara adalah 10

Berdasarkan Prinsip Inklusi-Eksklusi didapat hasilnya adalah 10000 + 10000 - 10 = 19990

A2. 101/10

Misalkan suatu barian memiliki tingkat kerapian x. Maka kita dapat menghitung berapa banyak barisan yang mungkin dengan teknik stars and bars. Terdapat 7 bebek jantan dan 13 bebek betina, berarti paling tingkat kerapian maksimum adalah 14 dan tingkat kerapian minimum adalah 1. Jadi kita dapat mencoba semua kemungkinan tingkat kerapian dari 2 hingga 15.

Untuk masing-masing tingkat kerapian:

• x = 1

  • Dimulai dari Jantan: ada (7 - 1 + 1 - 1)C(7 - 1) * (13 - 1 + 1 - 1)C(13 - 1)  = 6C6 * 12C12 = 1 * 1 = 1 barisan

  • Dimulai dari Betina: ada (7 - 1 + 1 - 1)C(7 - 1) * (13 - 1 + 1 - 1)C(13 - 1)  = 6C6 * 12C12 = 1 * 1 = 1 barisan

Untuk x = 1 ada sebanyak 1 + 1 = 2 barisan

Kontribusinya adalah 1 * 2 = 2

• x = 2:

  • Dimulai dari Jantan: ada (7 - 2 + 2 - 1)C(7 - 2) * (13 - 1 + 1 - 1)C(13 - 1) = 6C5 * 12C12 = 6 * 1 = 6

  • Dimulai dari Betina: ada (7 - 1 + 1 - 1)C(7 - 1) * (13 - 2 + 2 - 1)C(13 - 2) = 6C6 * 12C11 = 1 * 12 = 12

Untuk x = 2 ada sebanyak 6 + 12 = 18 barisan

Kontribusinya adalah 2 * 18 = 36

• x = 3:

  • Dimulai dari Jantan: ada (7 - 2 + 2 - 1)C(7 - 2) * (13 - 2 + 2 - 1)C(13 - 2) = 6C5 * 12C11 = 6 * 12 = 72

  • Dimulai dari Betina: ada (7 - 2 + 2 - 1)C(7 - 2) * (13 - 2 + 2 - 1)C(13 - 2) = 6C5 * 12C11 = 6 * 12 = 72

Untuk x = 3 ada sebanyak 72 + 72 = 144 barisan

Kontribusinya adalah 3 * 144 = 432

• x = 4:

  • Dimulai dari Jantan: ada (7 - 3 + 3 - 1)C(7 - 3) * (13 - 2 + 2 - 1)C(13 - 2) = 6C4 * 12C11 = 15 * 12 = 180

  • Dimulai dari Betina: ada (7 - 2 + 2 - 1)C(7 - 2) * (13 - 3 + 3 - 1)C(13 - 3) = 6C5 * 12C10 = 6 * 66 = 396

Untuk x = 4 ada sebanyak 180 + 396 = 576 barisan

Kontribusinya adalah 4 * 576 = 2304

• x = 5:

  • Dimulai dari Jantan: ada (7 - 3 + 3 - 1)C(7 - 3) * (13 - 3 + 3 - 1)C(13 - 3) = 6C4 * 12C10 = 15 * 66 = 990

  • Dimulai dari Betina: ada (7 - 3 + 3 - 1)C(7 - 3) * (13 - 3 + 3 - 1)C(13 - 3) = 6C4 * 12C10 = 15 * 66 = 990

Untuk x = 5 ada sebanyak 990 + 990 = 1980 barisan

Kontribusinya adalah 5 * 1980 = 9900

• x = 6:

  • Dimulai dari Jantan: ada (7 - 4 + 4 - 1)C(7 - 4) * (13 - 3 + 3 - 1)C(13 - 3) = 6C3 * 12C10 = 20 * 66 = 1320

  • Dimulai dari Betina: ada (7 - 3 + 3 - 1)C(7 - 3) * (13 - 4 + 4 - 1)C(13 - 4) = 6C4 * 12C9 = 15 * 220 = 3300

Untuk x = 6 ada sebanyak 1320 + 3300 = 4620 barisan

Kontribusinya adalah 6 * 4620 = 27720

• x = 7:

  • Dimulai dari Jantan: ada (7 - 4 + 4 - 1)C(7 - 4) * (13 - 4 + 4 - 1)C(13 - 4) = 6C3 * 12C9 = 20 * 220 = 4400

  • Dimulai dari Betina: ada (7 - 4 + 4 - 1)C(7 - 4) * (13 - 4 + 4 - 1)C(13 - 4) = 6C3 * 12C9 = 20 * 220 = 4400

Untuk x = 7 ada sebanyak 4400 + 4400 = 8800 barisan

Kontribusinya adalah 7 * 8800 = 61600

• x = 8:

  • Dimulai dari Jantan: ada (7 - 5 + 5 - 1)C(7 - 5) * (13 - 4 + 4 - 1)C(13 - 4) = 6C2 * 12C9 = 15 * 220 = 3300

  • Dimulai dari Betina: ada (7 - 4 + 4 - 1)C(7 - 4) * (13 - 5 + 5 - 1)C(13 - 5) = 6C3 * 12C8 = 20 * 495 = 9900

Untuk x = 8 ada sebanyak 3300 + 9900 = 13200 barisan

Kontribusinya adalah 8 * 13200 = 105600

• x = 9:

  • Dimulai dari Jantan: ada (7 - 5 + 5 - 1)C(7 - 5) * (13 - 5 + 5 - 1)C(13 - 5) = 6C2 * 12C8 = 15 * 495 = 7425 

  • Dimulai dari Betina: ada (7 - 5 + 5 - 1)C(7 - 5) * (13 - 5 + 5 - 1)C(13 - 5) = 6C2 * 12C8 = 15 * 495 = 7425

Untuk x = 9 ada sebanyak 7425 + 7425 = 14850 barisan

Kontribusinya adalah 9 * 14850 = 133650

• x = 10:

  • Dimulai dari Jantan: ada (7 - 6 + 6 - 1)C(7 - 6) * (13 - 5 + 5 - 1)C(13 - 5) = 6C1 * 12C8 = 6 * 495 = 2970

  • Dimulai dari Betina: ada (7 - 5 + 5 - 1)C(7 - 5) * (13 - 6 + 6 - 1)C(13 - 6) = 6C2 * 12C7 = 15 * 792 = 11880

Untuk x = 10 ada sebanyak 2970 + 11880 = 14850 barisan

Kontribusinya adalah 10 * 14850 = 148500

• x = 11:

  • Dimulai dari Jantan: ada (7 - 6 + 6 - 1)C(7 - 6) * (13 - 6 + 6 - 1)C(13 - 6) = 6C1 * 12C7 = 6 * 792 = 4752

  • Dimulai dari Betina: ada (7 - 6 + 6 - 1)C(7 - 6) * (13 - 6 + 6 - 1)C(13 - 6) = 6C1 * 12C7 = 6 * 792 = 4752

Untuk x = 11 ada sebanyak 4752 + 4752 = 9504 barisan

Kontribusinya adalah 11 * 9504 = 104544

• x = 12:

  • Dimulai dari Jantan: ada (7 - 7 + 7 - 1)C(7 - 7) * (13 - 6 + 6 - 1)C(13 - 6) = 6C0 * 12C7 = 1 * 792 = 792

  • Dimulai dari Betina: ada (7 - 6 + 6 - 1)C(7 - 6) * (13 - 7 + 7 - 1)C(13 - 7) = 6C1 * 12C6 = 6 * 924 = 5544

Untuk x = 12 ada sebanyak 792 + 5544 = 6336 barisan

Kontribusinya adalah 12 * 6336 = 76032

• x = 13:

  • Dimulai dari Jantan: ada (7 - 7 + 7 - 1)C(7 - 7) * (13 - 7 + 7 - 1)C(13 - 7) = 6C0 * 12C6 = 1 * 924 = 924

  • Dimulai dari Betina: ada (7 - 7 + 7 - 1)C(7 - 7) * (13 - 7 + 7 - 1)C(13 - 7) = 6C0 * 12C6 = 1 * 924 = 924

Untuk x = 13 ada sebanyak 924 + 924 = 1848 barisan

Kontribusinya adalah 13 * 1848 = 24024

• x = 14:

  • Dimulai dari Betina: ada (7 - 7 + 7 - 1)C(7 - 7) * (13 - 8 + 8 - 1)C(13 - 8) = 6C0 * 12C5 = 1 * 792 = 792

Untuk x = 14 ada sebanyak 792 barisan

Kontribusinya adalah 14 * 792 = 11088

Jumlah semuanya adalah 2 + 36 + 432 + 2304 + 9900 + 27720 + 61600 + 105600 + 133650 + 148500 + 104544 + 76032 + 24024 + 11088 = 705432

Banyaknya barisan yang mungkin ada sebanyak 20!/13!/7! = 77520

Jadi rata-ratanya adalah 705432/77520 = 91/10

A3. 1005

Dengan memilih ceiling(2009/2), dijamin kita dapat mengambil Permen dan Buah setidaknya setengah dari total keseluruhan. 

A4. 7

Karena terdapat 15C2 jalan dan masing-masing asisten menggunakan 15 jalan, maka ada 15C2 / 15 asisten maksimum yang mungkin, yaitu 7 asisten.

A5. 88

Misalkan banyaknya bebek Pak Dengklek adalah x, didapat 2 persamaan dan sebuah pertidaksamaan berikut

x ≡ 3 (mod 5)

x ≡ 0 (mod 11)

x ≤ 100

Ubah persaman 2 menjadi

x = 11y, untuk suatu bilangan bulat y

Substitusi ke dalam persamaan 1

11y ≡ 3 (mod 5)

y ≡ 3 (mod 5)

y = 5z + 3, untuk suatu bilangan bulat z

Substitusi kembali ke persamaan x = 11y

x = 11(5z + 3)

x = 55z + 33

x ≤ 100, maka x terbesar yang mungkin adalah ketika z = 1, didapat x = 88

A6. 36

Pertimbangkan kasus paling buruk yaitu kasus dimana Pak Dengklek hanya bergerak ke arah Utara, Timur, Utara, Timur, dan seterusnya. Disini akan ujung Utara dan Timur. Karena setiap 10 menit dapat berganti posisi dan 10 menit habis membagi 2 jam, maka bisa dibagi saja 1 jam untuk ke arah Utara dan 1 jam lagi untuk ke arah Timur. Didapat 3 km ke arah Utara dan 3 km ke arah Timur. Dengan cara yang sama, dibutuhkan juga 3 km ke arah Selatan dan 3 km ke arah Barat. Jadi dibutuhkan sebuah persegi dengan sisi sebesar 6 km. Luas arena olahraga sebesar 36 kilometer persegi.

A7. 3

Buat suatu graf dimana setiap kelas (verteks) akan memiliki sisi dengan verteks lain apabila kedua kelas tidak boleh bersamaan. Selanjutnya problem ini sama dengan problem Graph Coloring, yaitu mewarnai graf dengan warna seminimum mungkin sehingga tidak ada 2 warna sama untuk setiap 2 verteks yang terhubung. Dijamin dengan menggunakan 3 warna sudah paling optimal untuk mewarnai graf.

A8. 4

Ubah soal menjadi bentuk tabel agar lebih mudah dimengerti

Dari soal juga terdapat beberapa persamaan yaitu

9 + 15-b + c = 25

a + b + c = 16

9-a + 2 + c = 9

Setelah ketiga persamaan diselesaikan, akan didapat a = 7, b = 4, c = 5

Karena pertanyaan soal adalah variabel b, maka didapatkan jawaban 4

A9. 7

Dari 1 hingga 9 ada 9 digit.

Dari 10 hingga 99 ada 180 digit.

Dari 100 hingga 710 ada 1833 digit.

Jadi dari 1 hingga 710 sudah ada 2022 digit. Untuk digit ke 2023 ada pada angka 7.

A10. 3

Kwek bermain seri saat bertanding melawan Kwak dan Kwok. Jadi Kwek sudah mendapatkan 2 poin. Untuk mendapatkan 5 poin di akhir, Kwek harus mendapatkan 3 poin saat melawan Kwik.

Studi Kasus B1. Menjual Kentang

B1.1. 44

Berdasarkan peraturan nomor 1, semua kentang dengan bobot ≥ 6 pada truk B harus dipindahkan ke truk A. Jadi didapatkan total bobot yaitu 6 + 8 + 8 + 12 + 10 = 44.

B1.2. 38

Untuk mendapatkan total bobot minimum, nilai b harus sebesar mungkin hal ini karena adanya aturan nomor 1. Urutan kentang tidak penting, jadi bobot kentang pada masing-masing truk dapat diurutkan.

A = {2, 3, 5, 7, 8}

B = {5, 6, 8, 8, 10, 12}

Dapat dicoba untuk semua nilai b dari terbesar ke terkecil yang ada pada truk B lalu cek apakah pemindahan tersebut memenuhi peraturan nomor 2 dan nomor 3. Nilai b pertama yang memenuhi ketiga peraturan akan membantu kita mendapatkan pemindahan dengan total bobot yang minimum.

• b = 12

  • rata-rata bobot di A = (2 + 3 + 5 + 7 + 8 + 12) / 6 = 37/6

  • rata-rata bobot di B = (5 + 6 + 8 + 8 + 10) / 5 = 37/5

tidak memenuhi aturan nomor 3

• b = 10

  • rata-rata bobot di A = (2 + 3 + 5 + 7 + 8 + 12 + 10) / 7 = 47/7

  • rata-rata bobot di B = (5 + 6 + 8 + 8) / 4 = 27/4 

tidak memenuhi aturan nomor 3

• b = 8

  • rata-rata bobot di A = (2 + 3 + 5 + 7 + 8 + 12 + 10 + 8 + 8) / 9 = 7

  • rata-rata bobot di B = (5 + 6) / 2 = 11/2

memenuhi aturan nomor 2 dan 3

Jadi kita gunakan b = 8 dengan total bobot pemindahan adalah 12 + 10 + 8 + 8 = 38.

Soal Pemrograman

Dari soal nomor 2, kita telah mendapatkan observasi 

Untuk mendapatkan total bobot minimum, nilai b harus sebesar mungkin hal ini karena adanya aturan nomor 1

Kita dapat menggunakan observasi dan cara yang sama dengan soal nomor 2, yaitu melakukan iterasi untuk mendapatkan nilai b yang sebesar-besarnya yang tetap memenuhi peraturan nomor 2 dan nomor 3 kemudian menggunakan nilai b tersebut untuk mendapatkan total bobot minimum yang perlu dipindahkan.

Kompleksitas Waktu: O(N + M log M)

Contoh code:

#include <bits/stdc++.h>

using namespace std;

int main() {

   int N, M;

   cin >> N >> M;

   long long sumA = 0;

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

       int a;

       cin >> a;

       sumA += a;

   }

   long long sumB = 0;

   vector<int> B(M);

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

       cin >> B[i];

       sumB += B[i];

   }

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

   long long ans = -1, bobot = 0;

   if (sumA * M > sumB * N) {

       ans = 0;

   }

   for (int i = M - 1; i > 0 && ans == -1; i--) {

       bobot += B[i];

       sumB -= B[i];

       if (B[i] != B[i - 1]) {

           int pindah = M - i;

           if ((sumA + bobot) * (M - pindah) > sumB * (N + pindah)) {

               ans = bobot;

               break;

           }

       }

   }

   cout << ans << '\n';

   return 0;

}

Studi Kasus B2. Masa Pertumbuhan

B2.1. 2

• Pada akhir hari 0, tingginya 3 satuan.

• Pada awal hari 1, tingginya 3 + 2 = 5 satuan. Siram dengan air botol dengan nilai 4. Tingginya menjadi max(5, 4) = 5. Botol ini tidak berguna.

• Pada awal hari 2, tingginya 5 + 2 = 7 satuan. Siram dengan air botol dengan nilai 9. Tingginya menjadi max(7, 9) = 9. Botol ini berguna.

• Pada awal hari 3, tingginya 9 + 2 = 11 satuan. Siram dengan air botol dengan nilai 10. Tingginya menjadi max(11, 10) = 11. Botol ini tidak berguna. 

• Pada awal hari 4, tingginya 11 + 2 = 13 satuan. Siram dengan air botol dengan nilai 15. Tingginya menjadi max(13, 15) = 15. Botol ini berguna.

Jadi ada 2 botol air ajaib yang berguna.

B2.2. 3

Lakukan strategi greedy dengan memilih botol air ajaib dengan nilai A[i] yang terkecil dan berguna. Bukti untuk strategi greedy: jika kita memilih botol air ajaib yang A[i] cukup besar, maka botol air ajaib yang A[i] lebih kecil tidak akan bisa kita gunakan lagi. Agar lebih banyak botol yang bisa berguna yang bisa digunakan, maka gunakan botol air ajaib yang A[i] lebih kecil dahulu.

Botol-botol yang ada dapat kita urutkan terlebih dahulu.

A = {6, 9, 10, 11}

Lakukan pengambilan botol yang lebih optimal.

• Pada akhir hari 0, tingginya 4 satuan.

• Pada awal hari 1, tingginya 4 + 1 = 5 satuan. Siram dengan air botol dengan nilai 6. Tingginya menjadi max(5, 6) = 6. Botol ini berguna.

• Pada awal hari 2, tingginya 6 + 1 = 7 satuan. Siram dengan air botol dengan nilai 9. Tingginya menjadi max(7, 9) = 9. Botol ini berguna.

• Pada awal hari 3, tingginya 9 + 1 = 10 satuan. Jangan siram dengan air botol dengan nilai 10 karena botol ini tidak berguna. Siram dengan air botol dengan nilai 11. Tingginya menjadi max(10, 11) = 11. Botol ini berguna. 

• Untuk hari 4 dan seterusnya botol-botol yang tersisa tidak mungkin berguna.

Jadi ada 3 botol air ajaib yang berguna.

Soal Pemrograman

Lakukan strategi greedy dengan memilih botol air ajaib dengan nilai A[i] yang terkecil dan berguna. Bukti untuk strategi greedy: jika kita memilih botol air ajaib yang A[i] cukup besar, maka botol air ajaib yang A[i] lebih kecil tidak akan bisa kita gunakan lagi. Agar lebih banyak botol yang bisa berguna yang bisa digunakan, maka gunakan botol air ajaib yang A[i] lebih kecil dahulu. Jawaban kita adalah banyaknya botol air ajaib yang bisa kita pilih.

Kompleksitas Waktu: O(N log N)

Contoh code:

#include <bits/stdc++.h>

using namespace std;

int main() {

   int N, M, K;

   cin >> N >> M >> K;

   vector<int> A(N);

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

       cin >> A[i];

   }

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

   int ans = 0, id = 0;

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

       M += K;

       while (id < N && A[id] <= M) id++;

       if (id < N && A[id] > M) {

           M = A[id++];

           ans++;

       }

   }

   cout << ans << '\n';

   return 0;

}

Studi Kasus B3. Pembangkit Listrik

B3.1. 22

Perusahaan 1 dengan tarif 5 membangun pembangkit listrik di desa A yang memiliki tingkat kesulitan 3. Biaya untuk Perusahaan 1 adalah 5 x 3 = 15.

Perusahaan 2 dengan tarif 7 membangun pembangkit listrik di desa E yang memiliki tingkat kesulitan 1. Biaya untuk Perusahaan 2 adalah 7 x 1 = 7.

Total biaya yang diperlukan adalah 15 + 7 = 22.

B3.2. 19

Untuk beberapa desa yang terhubung, kita hanya perlu membangun 1 pembangkit listrik di desa yang tingkat kesulitan paling kecil. Total ada 2 pembangkit listrik yang akan kita bangun karena masing-masing dari desa {A, B, C, D} dan {E, F} telah terhubung.

Dari {A, B, C, D} tingkat kesulitan ada di desa B yaitu 2. Dari {E, F} tingkat kesulitan ada di desa E yaitu 1

2 tarif perusahaan termurah ada di perusahaan 2, yaitu 6 dan perusahaan 3, yaitu 7.

Jadi total biaya minimum dapat kita hitung dengan 2 x 6 + 1 x 7 = 19.

Soal Pemrograman

Gunakan algoritma Depth First Search beberapa kali yaitu iterasi untuk semua verteks, apabila verteks itu belum pernah dikunjungi sebelumnya maka kita akan mendapat suatu keterhubungan verteks baru. Lakukan Depth First Search pada verteks itu dan cari tingkat kesulitan terkecil dari beberapa verteks yang telah terhubung. Masukkan nilai tersebut ke sebuah array sebut saja array V.

Setelah iterasi selesai, urutkan array V dari terbesar ke terkecil Urutkan juga tarif perusahaan dari terkecil ke terbesar. Abaikan tarif untuk index yang lebih besar dari ukuran V karena perusahaan itu tidak akan digunakan. Namun apabila ukuran V lebih daripada banyaknya perusahaan, maka ada suatu komponen terhubung yang tidak dapat dibangun pembangkit listrik, yang menyebabkan jawaban adalah -1.

Total biaya minimum didapat pada perkalian tarif perusahaan dan array V untuk setiap indeks.

Kompleksitas Waktu: O(N log N + M log M)

Contoh code:

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1'000'000'000;

int x;

vector<int> a, b;

vector<vector<int>> adj;

vector<bool> vis;

void dfs(int u) {

   vis[u] = true;

   x = min(x, a[u]);

   for (auto &v : adj[u]) {

       if (!vis[v]) {

           dfs(v);

       }

   }

}

int main() {

   int n, m, k;

   cin >> n >> m >> k;

   a.resize(n);

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

       cin >> a[i];

   }

   b.resize(m);

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

       cin >> b[i];

   }

   adj.resize(n);

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

       int u, v;

       cin >> u >> v;

       --u; --v;

       adj[u].push_back(v);

       adj[v].push_back(u);

   }

   vector<int> V;

   vis.assign(n, false);

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

       if (!vis[i]) {

           x = INF;

           dfs(i);

           V.push_back(x);

       }

   }

   sort(V.rbegin(), V.rend());

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

   if (m < V.size()) {

       cout << "-1\n";

   } else {

       long long ans = 0;

       for (int i = 0; i < (int) V.size(); i++) {

           ans += 1LL * V[i] * b[i];

       }

       cout << ans << '\n';

   }

   return 0;

}

Studi Kasus B4. Mengumpulkan Artefak

B4.1. 12

Mobil Pak Dengklek akan berjalan dari koordinat 9 hingga 29. Beberapa artefak yang dapat Pak Dengklek ambil:

• Artefak pada posisi 12, bernilai 1

• Artefak pada posisi 15, bernilai 3

• Artefak pada posisi 21, bernilai 8

Jumlah dari semua artefak ini adalah 1 + 3 + 8 = 12.

B4.2. 13

Ada 4 jenis strategi:

• Ke arah kanan saja

• Ke arah kiri saja

• Ke arah kiri, lalu ke kanan

• Ke arah kanan, lalu ke kiri

Untuk strategi pertama, sudah dihitung pada soal nomor 1, yaitu jumlah nilainya adalah 12

Untuk strategi kedua, hanya akan didapatkan sebuah artefak yaitu pada koordinat 3, jumlah nilainya adalah 9

Untuk strategi ketiga, hanya perlu sampai koordinat 3 karena di sebelah kiri koordinat 3 sudah tidak ada artefak lagi, kemudian bergerak ke kanan. Koordinat terkanan paling jauh yang dapat Pak Dengklek tempuh adalah 3 + (20 - (9 - 3)) = 17. Jadi semua artefak yang koordinatnya x dimana 3 ≤ x ≤ 17, dapat diambil. Beberapa artefak yang diambil:

• Artefak pada posisi 3, bernilai 9

• Artefak pada posisi 12, bernilai 1

• Artefak pada posisi 15, bernilai 3

Total nilai artefak pada strategi ketiga ini adalah 9 + 1 + 3 = 13.

Untuk strategi keempat, dijamin tidak mungkin lebih optimal dari strategi ketiga, karena jika Pak Dengklek putar balik pada koordinat yang ≤ 17 total nilai artefak tidak akan melebihi total nilai artefak pada strategi ketiga. Jika Pak Dengklek putar balik pada koordinat > 17, maka artefak pada koordinat 3 tidak dapat diambil sehingga total nilai artefak akan lebih kecil dari strategi ketiga.

Jadi dari semua strategi yang ada, strategi ketiga dapat mewakili pengambilan jumlah terbesar nilai artefak yaitu 13.

Soal Pemrograman

Ada 4 strategi yang mungkin:

• Ke arah kanan saja

• Ke arah kiri saja

• Ke arah kiri lalu kanan

• Ke arah kanan lalu kiri

Untuk strategi pertama dan kedua, dapat dihitung secara langsung koordinat tempat Pak Dengklek berhenti, lalu jumlahkan semua artefak yang berada pada rentang koordinat Pak Dengklek mulai dan Pak Dengklek berhenti.

Untuk strategi ketiga dan keempat, ada sebuah observasi yaitu putar balik pada koordinat artefak selalu lebih optimal. Bukti, jika Pak Dengklek tidak putar balik pada koordinat artefak, maka akan ada beberapa bensin terbuang dari koordinat artefak terakhir yang diambil sampai koordinat Pak Dengklek putar balik. Padahal bensin itu dapat kita gunakan untuk menambah panjang terjauh untuk arah sebaliknya yang mungkin bisa digunakan untuk meraih artefak di arah sebaliknya.

Dari observasi di atas, kita bisa mencoba semua koordinat putar balik yang mungkin yaitu di koordinat artefak (selama bensin masih cukup) lalu mencari koordinat berakhir Pak Dengklek yaitu dengan menambah perhitungan dengan sisa bensin. Untuk mempercepat perhitungan ini, kita dapat menggunakan prefix sum serta binary search untuk mendapatkan indeks dari artefak terjauh yang mungkin diraih setelah putar balik.

Jawaban kita adalah jumlah terbesar nilai artefak yang mungkin dari semua strategi.

Tambahan tips implementasi: kurangkan semua koordinat dengan x akan lebih memudahkan karena koordinat Pak Dengklek selalu 0, untuk a[i] > 0 berarti koordinat artefak ada di sebelah kanan Pak Dengklek, untuk a[i] < 0 berarti koordinat artefak ada di sebelah kiri Pak Degklek.

Kompleksitas Waktu: O(N log N)

Contoh code:

#include <bits/stdc++.h>

using namespace std;

int main() {

   int n, k, x;

   cin >> n >> k >> x;

   vector<int> a(n + 2), b(n + 2);

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

       cin >> a[i];

       a[i] -= x;

   }

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

       cin >> b[i];

   }

   vector<long long> pref(n + 2);

   pref[0] = 0;

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

       pref[i] = pref[i - 1] + b[i];

   }

   long long ans = 0;

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

       if (a[i] == 0) {

           ans += b[i];

       }

   }

   // kanan

   long long newans = 0;

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

       if (0 <= a[i] && a[i] <= k) {

           newans += b[i];

       }

   }

   ans = max(ans, newans);

   // kiri

   newans = 0;

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

       if (-k <= a[i] && a[i] <= 0) {

           newans += b[i];

       }

   }

   ans = max(ans, newans);

   // putar balik

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

       int fuel = k - abs(a[i]), stop, id;

       if (fuel < 0) continue;

       if (a[i] > 0) { // kanan - kiri

           stop = min(a[i] - fuel, 0);

           id = lower_bound(a.begin() + 1, a.begin() + n + 1, stop) - a.begin();

       } else { // kiri - kanan

           stop = max(a[i] + fuel, 0);

           id = upper_bound(a.begin() + 1, a.begin() + n + 1, stop) - a.begin() - 1;

       }

       id = min(id, n);

       id = max(id, 1);

       int l = min(id, i);

       int r = max(id, i);

       ans = max(ans, pref[r] - pref[l - 1]);

   }

   cout << ans << '\n';

   return 0;

}

Studi Kasus B5. Membeli Oleh-Oleh

B5.1. 0

Tidak dapat diterapkan karena dari kota 2 ada percabangan ke kota 3 dan kota 4. Pak Dengklek tidak mungkin mengunjungi kota 2 sebanyak lebih dari sekali jadi salah satu dari kota 3 dan kota 4 tidak dapat dikunjungi dan tidak dapat dibeli oleh-olehnya.

B5.2. 17

Rencana pembelian tersebut antara lain pada kota:

• {1}

• {2}

• {3}

• {4}

• {5}

• {6}

• {1, 2}

• {1, 3}

• {1, 4}

• {1, 5}

• {1, 6}

• {2, 3}

• {2, 4}

• {5, 6}

• {1, 2, 3}

• {1, 2, 4}

• {1, 5, 6}

Soal Pemrograman

Dynamic Programming on Tree yaitu untuk menghitung banyaknya rencana perjalanan menggunakan 3 dimensi:

• Kota sekarang

• Jumlah uang yang digunakan untuk membeli oleh-oleh dari kota 1 hingga kota sekarang

• Apakah membeli oleh-oleh pada kota sekarang

Untuk base case dapat menggunakan root atau kota 1

• dp[1]][0][0] = 1, karena ada 1 cara untuk tidak membeli oleh-oleh pada kota 1 dan uang yang digunakan adalah 0. 

• dp[1][A[1]][1] = 1, karena ada 1 cara untuk membeli oleh-oleh pada kota 1 dan uang yang digunakan adalah A[1]

Untuk transisi,

• dp[u][uang][0] = dp[parent u][uang][0] + dp[parent u][uang][1], karena tidak membeli apapun pada kota u.

• dp[u][uang][1] = dp[parent u][uang - A[u]][0] + dp[parent u][uang - A[u]][1], karena jika membeli pada kota u akan dibutuhkan uang sebanyak A[u]

Untuk hitung akhir jumlah semua rencana pembelian oleh-oleh dapat ditinjau untuk semua dp yang sedang membeli oleh-oleh pada kota sekarang. Dapat diasumsikan sebagai kota tersebut adalah kota terakhir yang dibeli oleh-olehnya. Gunakan prefix sum juga untuk mendapatkan hasil akhir.

Kompleksitas Waktu: O(NM)

Contoh code:

#include <bits/stdc++.h>

using namespace std;

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

int N, M;

int A[101];

int dp[101][100'001][2];

int sum[100'001];

vector<vector<int>> adj;

void dfs(int u, int p) {

   if (u == 0) {

       dp[0][0][0] = 1;

       dp[0][A[0]][1] = 1;

   } else {

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

           dp[u][i][0] = (dp[p][i][0] + dp[p][i][1]);

           if (dp[u][i][0] >= mod) dp[u][i][0] -= mod;

           if (i >= A[u]) {

               dp[u][i][1] = (dp[p][i - A[u]][0] + dp[p][i - A[u]][1]);

               if (dp[u][i][1] >= mod) dp[u][i][1] -= mod;

           }

       }

   }

   for (auto &v : adj[u]) {

       if (v == p) continue;

       dfs(v, u);

   }

}

int main() {

   cin >> N >> M;

   adj.assign(N, vector<int>());

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

       cin >> A[i];

   }

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

       int u, v;

       cin >> u >> v;

       --u; --v;

       adj[u].push_back(v);

       adj[v].push_back(u);

   }

   dfs(0, -1);

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

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

           sum[j] += dp[i][j][1];

           if (sum[j] >= mod) sum[j] -= mod;

       }

   }

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

       sum[i] += sum[i - 1];

       if (sum[i] >= mod) sum[i] -= mod;

   }

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

       cout << sum[i] << '\n';

   }

   return 0;

}