Pembahasan OSN-P (KSN-P) 2020 (Informatika)

Written by: 

• Leonardo Dahendra (Drakozs)

Reviewed by: 

• Jiriki Joeng (kizu)

• Christoffer Edbert Karuniawan (Chrisedyong)

*warna berdasarkan max rating Codeforces per Jul 2025

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

Bagian A: Analitika & Logika 

A1. 17

Jadi disini untuk urutan angkanya, dia mulai dari 4^0, 4^1, 4^1 + 4^0, 4^2, 4^2 + 4^0, ..... Disini urutan angkanya sendiri sama dengan urutan angka dalam bilangan biner basis 2 yang sering dipakai, untuk basis 2 sendiri bentuknya itu 2^0, 2^1, 2^1 + 2^0, 2^2, 2^2 + 2^0, .... Yang jika ditulis dalam bilangan biner akan menjadi 0001, 0010, 0011, 0100, 0101. Jika sudah mengerti sampai disini, kita bisa tahu bahwa untuk mengetahui angka ke 2020. Kita tinggal cari nilai biner dari 2020, kemudian ubah dari basis 2 menjadi basis 4. Biner dari 2020 yaitu 0111 1110 0100. Ketika konversikan, kita tinggal ubah saja dari 2^2 + 2^5 + 2^6 + ... + 2^10 menjadi 4^2 + 4^5 + 4^6 + ... + 4^10.

Nanti akan menjadi 16 + 1024 + 4096 + 16384 + 65536 + 262144 + 1048576 = 1397776. Ketika dimodulo 31 akan mendapatkan hasil 1397776 % 31 = 17

A3. Farah

Pertama, untuk pernyataan yang menyatakan "Pernyataan X bernilai benar", itu sudah pasti salah. Karena jika pernyataan mereka benar, maka akan terdapat 1 pernyataan lagi, yaitu pernyataan si X yang juga harus bernilai benar. Sama juga dengan pernyataan dimana terdapat pernyataan lain yang bilang mereka benar, misal Y mengatakan "Pernyataan X bernilai benar" maka kedua X dan Y sudah pasti salah, karena jika salah satunya benar, maka kedua pernyataan wajib benar. Ini juga berlaku untuk yang 3 orang, seperti pernyataan Danis, Budi, dan Albert. Jika salah satu pernyataan dari mereka benar, maka ketiga pernyataannya wajib benar. Karena itu pernyataan yang tersisa hanyalah pernyataan Farah

A4. 2

Hanya terdapat 2 kemungkinan yang bisa, yaitu Kwik dan Kwok saja yang ke Bandung atau Kwak, Kwik, dan Kwok yang ke Bandung. Perhatikan bahwa di aturan kedua, disebut bahwa hanya tepat salah satu dari Kwik dan Kwek yang akan ke Bandung. Namun, pada aturan ketiga, dikatakan bahwa jika Kwek ke Bandung, maka Kwak dan Kwok wajib ikut, dimana sesuai aturan pertama, jika Kwak ikut, maka Kwik juga ikut. Jadi jika Kwek ikut, maka tidak akan mungkin untuk memenuhi keempat atura, maka dari itu, Kwek tidak mungkin ikut ke Bandung. Dengan ini, dapat dipastikan juga bahwa Kwik wajib ikut ke Bandung sesuai aturan kedua. Dari aturan keempat, kita juga dapat simpulkan bahwa Kwok juga wajib ikut, karena jika Kwok tidak ikut, Kwik tidak boleh ikut. Yang terakhir sisa Kwak, untuk Kwak sendiri, dia bisa saja ikut maupun tidak, keduanya akan tetap memenuhi aturan(Jika Kwak ikut, Kwik wajib ikut namun tidak sebaliknya, bisa saja Kwik ikut tapi Kwak tidak ikut).

A5.  TRUE FALSE FALSE

Ga perlu observasi apapun, langsung dikerjakan aja, yang penting cuma mengerti aljabar boolean dan bedanya AND, OR, sama NOT. Kerjakannya yang P dan Q dulu baru ujungnya bisa kerja yang R

P = (True and (not True)) or ((True or (not True)) and (not False))

P = (True and False) or ((True or False) and True)

P = False or (True and True)

P = False or True

P = True

Q = ((not A) or (not B)) and (((not C) and D) or (not E))

Q = ((not True) or (not True)) and (((not True) and True) or (not False))

Q = (False or False) and ((False and True) or True)

Q = False and (False or True)

Q = False and True

Q = False

R = P and Q

R = True and False

R = False

A6. 22

Pertanyaan ini intinya merupakan pertanyaan convex hull untuk mendapatkan keliling paling kecil yang menutupi keseluruhan titik. Jika kita sudah mengetahui tentang convex hull, kita bisa menggunakan beberapa algoritma untuk menyelesaikan masalah ini, salah satunya bisa menggunakan graham scan. Namun jika tidak mengetahui tentang convex hull, kita juga bisa gambarkan saja koordinat setiap titik lalu membayangkan apa yang terjadi jika kita menarik sebuah karet yang menutupi keseluruhan titik, lalu melepaskan karet tersebut, pastinya karet tersebut akan menyentuh bagian luar dari titik-titik tersebut. Dari situ kita bisa membuat gambaran garis-garisnya dan menghitung kelilingnya. Untuk koordinatnya akan terlihat seperti ini

Dengan menggunakan algoritma graham scan, atau nguli saja juga bisa, nanti akan didapatkan garis seperti ini

Setelah ini kita bisa tinggal menghitung panjang setiap garisnya saja, dimulai dari garis pada titik (0, 0) ke (4, 0). Hasilnya yaitu 

= 4 + 8 + 1 + sqrt(4^2 +3^2) + 4

= 17 + sqrt(25)

= 17 + 5

= 22

A7. 46

Pertanyaan dari soal ini sebenarnya hanya menanyakan max flow dari node 1 ke node 9. Masalah ini merupakan masalah max flow min cut yang bisa diselesaikan dengan mencari maximum flow dari node 1 ke node 9, dan jawaban akhirnya merupakan maximum flow tersebut. Untuk perhitungan maximum flownya akan didapatkan seperti berikut

Didapatkan jawaban akhir dari soal ini adalah 23 + 23 = 46. Namun jika tidak mengetahui mengenai maximum flow, kita juga bisa nguli saja untuk menemukan jawabannya, untuk edge yang perlu dihancurkan yaitu edge 2-5, 2-7, 4-7, 3-5, 3-8, 6-8

A8. 6

Dari pernyataan soal, maka dapat disimpulkan bahwa setiap bebek yang berwarna sama harus diurutkan bersamaan dalam 1 kelompok, dan dikarenakan setiap bebek yang warnanya sama tidak bisa dibedakan, urutan seperti M1, M2 atau M2, M1 itu sama aja, dengan M1 = bebek merah pertama, M2 = bebek merah kedua. Disini jadinya jumlah dari bebeknya sendiri tidak penting, karena tidak akan memengaruhi hasil akhirnya, misal terdapat 2 bebek merah, pasti barisannya akan seperti ini M M. Sama juga jika terdapat 5 bebek merah, barisannya akan tetap sama. Jadi ini sama saja dengan bertanya cara memposisikan 3 warna berbeda, yang jadinya permutasi dari 3 warna, P(3, 3) = 3!/0! = 6 yaitu

M M M M B B B H H

M M M M H H B B B

B B B M M M M H H

B B B H H M M M M

H H M M M M B B B

H H B B B M M M M

A9. 22020096

Pertama kita perlu pahami dulu bahwa angka 1048576 itu bukan angka sembarang, namun merupakan nilai yang didapatkan dari 2^20. Karena itu angka ini akan terus dibagi 2 menjadi 2^19, 2^18, ..., 2^0. Dari ini kita bisa mencoba mengerjakan dari bentuk paling sederhananya terlebih dahulu untuk mendapatkan pola

n = 1, f(n) = 1

n = 2, f(n) = 1 * 2 + 2 = 4

n = 4, f(n) = 4 * 2 + 4 = 12

n = 8, f(n) = 12 * 2 + 8 = 32

n = 16, f(n) = 32 * 2 + 16 = 80

Dari sini akan terlihat pola bahwa nilai untuk suatu n dimana n bisa dituliskan dalam bentuk 2^k bisa didapatkan dengan rumus (k + 1) * n. Rumus ini benar untuk kelima n yang telah dicoba dan juga akan benar untuk n lain yang memenuhi bentuk 2^k. Untuk n = 1048576, maka nilainya yaitu
(20 + 1) * 1048576 = 22020096

Jika ingin mencari cara yang lebih pasti untuk mendapatkan rumusnya juga bisa dengan substitusi. Untuk formula awal yaitu

f(n) = f(n / 2) * 2 + n

Nanti untuk f(n / 2) maka akan menjadi seperti ini

f(n / 2) = f(n / 4) * 2 + n / 2

Coba masukkan kedalam f(n)

f(n) = (f(n / 4) * 2 + n / 2) * 2 + n

f(n) = f(n / 4) * 4 + n + n

f(n) = f(n / 4) * 4 + 2 * n

Untuk f(n / 4)

f(n / 4) = f(n / 8) * 2 + n / 4

Masukkan ke f(n)

f(n) = (f(n / 8) * 2 + n / 4) * 4 + 2 * n

f(n) = f(n / 8) * 8 + n + 2 * n

f(n) = f(n / 8) * 8 + 3 * n

Dari ketiga ini akan didapatkan pola yang lebih pasti yaitu

f(n) = f(n / 2^k) * 2^k + k * n

Selanjutnya kita cari, kapan fungsi f(n / 2^k) ini akan berhenti, fungsi ini akan berhenti ketika n / 2^k = 1

n / 2^k = 1

n = 2^k

k = log2(n)

Masukkan kembali ke rumus awal

f(n) = f(n / 2^k) * 2^k + k * n

f(n) = f(2^k / 2^k) * n + log2(n) * n

f(n) = f(1) * n + log2(n) * n

f(n) = n + log2(n) * n

f(n) = (log2(n) + 1) * n

Yang hasilnya sama dengan rumus yang didapatkan diawal

A10. 8

Intinya cuma ditanyain LIS(Longest Increasing Subsequence) dari list angka. Buat kerjainnya bisa pakai cara binary search biar cepat. Kita tuliskan angkanya satu", jika angkanya lebih besar dari angka terakhir, kita masukkan ke list, tapi jika lebih kecil, kita ganti angka terkecil yang lebih besar dari angka baru dengan angka baru tersebut. Cara ini memastikan kita dapat mencari panjang maksimum dengan efisien, meskipun listnya sendiri mungkin isinya salah. Jika disimulasikan nanti hasilnya gini

Angka: 2, List: 2

Angka: 14, List: 2 14

Angka: 7, List: 2 7

Angka: 20, List: 2 7 20

Angka: 5, List: 2 5 20

Angka: 3, List: 2 3 20

Angka: 8, List: 2 3 8

Angka: 11, List: 2 3 8 11

Angka: 18, List: 2 3 8 11 18

Angka: 4, List: 2 3 4 11 18

Angka: 10, List: 2 3 4 10 18

Angka: 12, List: 2 3 4 10 12

Angka: 1, List: 1 3 4 10 12

Angka: 6, List: 1 3 4 6 12

Angka: 9, List: 1 3 4 6 9

Angka: 19, List: 1 3 4 6 9 19

Angka: 15, List: 1 3 4 6 9 15

Angka: 16, List: 1 3 4 6 9 15 16

Angka: 13, List: 1 3 4 6 9 13 16

Angka: 17, List: 1 3 4 6 9 13 16 17

Hasil dari angka-angkanya sendiri mungkin salah, namun panjang yang didapatkan sudah dipastikan benar yaitu 8

Studi Kasus B1: Lari Jauh 

B1.1. 7

Posisi patok warna hijau = 4 + 6 + 11 = 21

Agar bebek bisa mencapai atau melewati patok warna hijau, berarti untuk nilai Bi nya harus minimal 21. Terdapat 7 bebek yang memenuhi Bi >= 21

B1.2. 1

Posisi patok warna hitam = 4 + 6 + 11 + 18 + 12 = 51

Disini hanya terdapat 1 bebek saja yang nilai Bi >= 51

B1.3. 1

Disini kita perlu mencari jarak maksimal antara patok biru dan hitam dimana jumlah bebek yang melewatinya masih maksimal. Kita coba dulu jika jaraknya 1 untuk mengetahui target jumlah bebek kita berapa.

Jarak patok hitam = 4 + 6 + 11 + 18 + 1 = 40

Jumlah bebek yang berhasil melewati patok hitam = 3

Untuk mengetahui jarak maksimal yang bisa diberikan tanpa membuat jumlah bebek yang melewati patok hitam berkurang, kita lihat saja Bi minimal dari ketiga bebek yang berhasil lewat, disini Bi minimalnya yaitu 40. Karena bebek ini sudah berhenti tepat di patok hitam saat ini, jika kita membuat jarak patok hitam dan biru semakin besar, maka jumlah bebek yang bisa melewati pasti berkurang, karena itu jarak patok hitam dan biru wajib 1

Soal Pemrograman Subsoal 1

Untuk setiap bebek, kita bisa menghitung jumlah patok yang bisa dilewatinya dengan looping semua patok yang ada dari awal sampai akhir, dan berhenti ketika bebek tersebut sudah tidak bisa melewati patok sekarang.

Kompleksitas: O(N * K)

#include<bits/stdc++.h>

using namespace std;

int main(){

   int n, k;

   cin >> n >> k;

   vector<int> patok(n);

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

       cin >> patok[i];

   }

   vector<int> bebek(k);

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

       int bi;

       cin >> bi;

       bebek[i] = bi;

   }

   vector<int> jawaban(k, 0);

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

       int jarak = 0;

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

           if (jarak + patok[j] <= bebek[i]){

               jawaban[i] = j + 1;

           }

           jarak += patok[j];

       }

   }

   for (int i = 0; i < k; i++) cout << jawaban[i] << "\n";

   return 0;

}

Soal Pemrograman Subsoal 2

Perhatikan bahwa, jika terdapat suatu bebek i dan bebek j dimana Bi <= Bj maka jika bebek i dapat melewati patok ke x, maka bebek ke j juga akan dapat melewati patok ke x. Dengan observasi ini, daripada kita menghitung ulang untuk setiap bebek, kita bisa hitung mulai dari bebek dengan Bi terendah, lalu untuk bebek berikutnya, kita lanjutkan dari patok terakhir yang bisa dilewati oleh bebek ke i. Dengan cara ini kita tidak akan perlu menghitung setiap patok untuk setiap bebek yang ada.

Kompleksitas: O(N + K log K)

#include<bits/stdc++.h>

using namespace std;

int main(){

   int n, k;

   cin >> n >> k;

   vector<int> patok(n);

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

       cin >> patok[i];

   }

   vector<pair<int, int>> bebek(k);

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

       int bi;

       cin >> bi;

       bebek[i] = {bi, i};

   }

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

   int posisi = 0;

   int jarak = 0;

   vector<int> jawaban(k);

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

       while(posisi < n && bebek[i].first >= jarak + patok[posisi]){

           jarak += patok[posisi];

           posisi++;

       }

       jawaban[bebek[i].second] = posisi;

   }

   for (int i = 0; i < k; i++) cout << jawaban[i] << "\n";

   return 0;

}

Studi Kasus B2: Lampu Hias Warna Warni

B2.1. 11

Untuk membuat barisan lampu maksimal, kita bisa pilih 3 lampu yang paling banyak yaitu L, N, I. Kemudian kita mulai saja dari lampu yang jumlahnya paling banyak, kedua paling banyak, dan yang paling dikit dari ketiganya, dengan cara ini kita pasti akan menemukan panjang barisan maksimal yaitu 11 dengan urutannya L N I L N I L N I L N.

B2.2. 24

Disini, untuk urutan setelah 3 lampu pertama tidak penting, karena jika urutan 3 lampu pertama telah ditentukan, hanya terdapat 1 kemungkinan cara untuk menentukan posisi sisa lampunya. Terdapat 4 jenis lampu yang bisa kita gunakan, dimana untuk 3 lampu pertama, setiap lampu wajib unik, ini kita bisa jadikan sebuah soal permutasi, untuk posisi pertama, terdapat 4 jenis lampu yang dapat kita pilih, untuk posisi kedua terdapat 3 jenis lampu, dan untuk posisi ketiga terdapat 2 jenis lampu. Jadi total kemungkinan barisan lampu yang dapat dibuat yaitu 4 * 3 * 2 = 24 kemungkinan

B2.3. 8

Jika lampu L mati, maka kita hanya bisa menggunakan lampu N, I, dan O. Kita mulai dari lampu yang jumlahnya paling banyak sampai paling sedikit. Nanti akan didapatkan panjang barisan maksimal yaitu 8 dengan urutannya N I O N I O N I.

Soal Pemrograman Subsoal 1

Karena disini N <= 100, kita bisa coba saja semua kemungkinan pilihan lampu yang ada, setelah memilih 3 lampu berbeda, kita cek jumlah warna dari setiap lampu, lalu coba bikin barisan terpanjang dari ketiga jenis lampu tersebut, untuk lampu di urutan pertama tentunya menggunakan lampu dengan jumlah terbanyak, lalu kedua terbanyak, dan ketiga menggunakan yang jumlahnya paling sedikit.

Kompleksitas: O(N^3)

#include<bits/stdc++.h>

using namespace std;

int main(){

   int n;

   cin >> n;

   string s;

   cin >> s;

   vector<int> jumlah(26, 0);

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

       int posisi = s[i] - 'A';

       jumlah[posisi]++;

   }

   int jawaban = -1;

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

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

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

               if (s[i] == s[j] || s[j] == s[k] || s[i] == s[k]) continue;

               int pos1 = s[i] - 'A', pos2 = s[j] - 'A', pos3 = s[k] - 'A';

               int minimum = min(jumlah[pos1], min(jumlah[pos2], jumlah[pos3]));

               int total = minimum * 3;

               if (jumlah[pos1] > minimum) total++;

               if (jumlah[pos2] > minimum) total++;

               if (jumlah[pos3] > minimum) total++;

               jawaban = max(jawaban, total);

           }

       }

   }

   cout << jawaban << "\n";

   return 0;

}

Soal Pemrograman Subsoal 2

Perhatikan bahwa memilih jenis lampu dengan jumlah terbanyak pasti bakal lebih menguntungkan daripada pilih yang jumlahnya lebih sedikit. Dengan observasi ini, daripada mencoba semua kemungkinan yang ada, kita bisa pilih saja 3 jenis lampu dengan jumlah terbanyak, lalu membuat barisan lampu dengan 3 jenis tersebut.

Kompleksitas: O(N)

#include<bits/stdc++.h>

using namespace std;

int main(){

   int n;

   cin >> n;

   string s;

   cin >> s;

   vector<int> jumlah(26, 0);

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

       int posisi = s[i] - 'A';

       jumlah[posisi]++;

   }

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

   int jawaban = -1;

   if (jumlah[2] == 0){

       cout << "-1\n";

       return 0;

   }

   int minimum = jumlah[2];

   jawaban = minimum * 3;

   if (jumlah[0] > minimum) jawaban++;

   if (jumlah[1] > minimum) jawaban++;

   cout << jawaban << "\n";

   return 0;

}

Studi Kasus B3: Kerja Freelance

B3.1. 6

Jika honor yang didapatkan sama untuk setiap kegiatan, maka ini jadinya sama saja dengan Activity Selection Problem yang bisa diselesaikan dengan greedy. Observasinya, pasti akan lebih untung untuk menyelesaikan pekerjaan yang waktu selesainya paling awal, hal ini karena tidak peduli dengan durasinya, jika kita bisa menyelesaikan sebuah tugas lebih cepat, kita pastinya akan punya lebih banyak waktu untuk pekerjaan berikutnya. Contohnya pekerjaan yang mulai di hari 1 dan selesai di hari 10, lalu pekerjaan kedua yang mulai di hari 9 dan selesai di hari 11. Meskipun pekerjaan kedua durasinya jauh lebih singkat, dengan memilih pekerjaan pertama, setelah selesai honor kita akan bertambah 1 dan kita dapat mencari pekerjaan berikutnya asalkan hari mulainya > 10, jika memilih pekerjaan kedua, honor akan bertambah 1 dan kita dapat mencari pekerjaan berikutnya asalkan hari mulainya > 11, tentunya lebih menguntungkan untuk mengambil pekerjaan yang selesai di hari 10 daripada 11. Dengan cara ini, maka kita akan memilih pekerjaan A, D, C, E, F, dan H jadi totalnya 6 pekerjaan.

B3.2. 30000

Untuk soal ini, kita diminta untuk mencari penghasilan maksimum, dimana setiap hari kerja memberikan 1000 rupiah, dengan kata lain, kita diminta untuk mencari total hari maksimum dari semua pekerjaan yang diambil. Untuk soal ini tidak terdapat solusi greedy, untuk mendapatkan jawabannya, kita bisa menggunakan Dynamic Programming(DP). Pertama kita urutkan dulu setiap kegiatan berdasarkan waktu selesainya kapan, lalu untuk setiap kegiatan dari yang paling awal, kita cari total hari maksimum yang bisa didapatkan jika harinya cuma sampai disitu. Untuk transisinya berarti kita akan ambil max(DP[pekerjaan sebelumnya], jumlah hari pekerjaan sekarang + DP[pekerjaan terakhir yang tidak bertabrakan]). Jika dikerjakan akan menjadi seperti ini

DP[A] = max(0, 10 + 0) = 10

DP[D] = max(10, 5 + DP[A]) = 15 

DP[C] = max(15, 2 + DP[D]) = 17

DP[E] = max(17, 2 + DP[C]) = 19

DP[B] = max(19, 5 + DP[D]) = 20

DP[F] = max(20, 7 + DP[B]) = 27

DP[H] = max(27, 3 + DP[F]) = 30

DP[G] = max(30, 3 + DP[F]) = 30

Dari sini didapatkan bahwa total hari maksimal yang bisa didapatkan yaitu 30 dengan penghasilan 30000

B3.3. 1675000

Untuk soal ini, kita bisa menggunakan cara yang sama dengan soal sebelumnya, hanya saja untuk nilai dari tiap pekerjaan diganti dengan penghasilan tetap

DP[A] = max(0, 200000 + 0) = 200000 

DP[D] = max(200000 , 350000 + DP[A]) = 550000

DP[C] = max(550000, 175000 + DP[D]) = 725000

DP[E] = max(725000, 400000 + DP[C]) = 1125000

DP[B] = max(1125000, 150000 + DP[D]) = 1125000

DP[F] = max(1125000, 250000 + DP[B]) = 1375000

DP[H] = max(1375000, 300000 + DP[F]) = 1675000

DP[G] = max(1675000, 185000 + DP[F]) = 1675000

Didapatkan jawaban akhir yaitu 1675000

Soal Pemrograman Subsoal 1

Untuk menyelesaikan soal ini, kita bisa menggunakan DP dengan 2 state, state pertama untuk menyimpan index dari pekerjaan saat ini, dan state kedua untuk menyimpan hari selesai terakhir sejauh ini. Pertama kita perlu mengurutkan setiap pekerjaan dari waktu selesai paling awal sampai paling akhir, kemudian untuk setiap pekerjaan yang ada, kita punya 2 pilihan, yaitu mengambil pekerjaan ini, atau melewati pekerjaan ini dengan harapan akan mendapatkan pekerjaan yang bernilai lebih besar kedepannya. Tentunya kita hanya bisa mengambil pekerjaan tersebut jika hari selesai terakhir sejauh ini tidak bertabrakan dengan pekerjaan yang ingin kita ambil saat ini.

Kompleksitas: O(M log M + M * Emax)

#include<bits/stdc++.h>

#define ll long long

#define MAXN 15000

using namespace std;

ll solve(int m, vector<vector<int>> &pekerjaan, vector<vector<ll>> &dp, int index, int hariSelesai){

   if (index >= m) return 0;

   if (dp[index][hariSelesai] != -1) {

       return dp[index][hariSelesai];

   }

   if (hariSelesai >= pekerjaan[index][1]) {

       return dp[index][hariSelesai] = solve(m, pekerjaan, dp, index + 1, hariSelesai);

   }

   ll skipPekerjaan = solve(m, pekerjaan, dp, index + 1, hariSelesai);

   ll ambilPekerjaan = solve(m, pekerjaan, dp, index + 1, pekerjaan[index][0]) + pekerjaan[index][2];

   return dp[index][hariSelesai] = max(skipPekerjaan, ambilPekerjaan);

}

int main(){

   int m;

   cin >> m;

   vector<vector<int>> pekerjaan(m);

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

       int s, e, p;

       cin >> s >> e >> p;

       pekerjaan[i] = {e, s, p};

   }

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

   vector<vector<ll>> dp(m, vector<ll>(MAXN + 1, -1));

   cout << solve(m, pekerjaan, dp, 0, 0) << "\n";

   return 0;

}

Soal Pemrograman Subsoal 2

Daripada mencoba setiap pekerjaan satu per satu secara berurutan untuk menentukan jawaban akhir, kita bisa mencoba mengecek setiap hari selesai yang mungkin saja. Jadi jika hari berakhirnya cuma sampai hari 1, berapa jawaban maksimalnya, jika cuma sampai hari 2, berapa jawaban maksimalnya, dst sampai hari terakhir yang mungkin. Dengan cara ini, kita hanya perlu menyimpan 1 state didalam DP kita, yaitu jawaban maksimal jika hari terakhirnya merupakan hari ke i. Untuk setiap pekerjaan, kita bisa lihat saja pekerjaan apa saja yang selesai di hari i, dan mengambil jawaban maksimal antara DP[i - 1] atau DP[hari mulai pekerjaan - 1] + nilai dari pekerjaan saat ini.

Kompleksitas: O(M + Emax)

#include<bits/stdc++.h>

#define ll long long

#define HARIMAKSIMUM 15000

using namespace std;

int main(){

   int m;

   cin >> m;

   vector<vector<pair<int, int>>> hariSelesai(HARIMAKSIMUM + 1);

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

       int s, e, p;

       cin >> s >> e >> p;

       hariSelesai[e].push_back({s, p});

   }

   vector<ll> dp(HARIMAKSIMUM + 1, 0);

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

       dp[i] = dp[i - 1];

       for (auto &pekerjaan : hariSelesai[i]){

           dp[i] = max(dp[i], dp[pekerjaan.first - 1] + pekerjaan.second);

       }

   }

   cout << dp[HARIMAKSIMUM] << "\n";

   return 0;

}

Studi Kasus B4: Katak Super

B4.1. 69

Karena tidak mempunyai kekuatan super, maka katak hanya bisa melompat sekali ke kiri atau sekali ke kanan. Perhatikan bahwa selalu lebih optimal untuk melompat ke kanan, jika katak melompat ke kiri sekali, untuk bisa bergerak ke kanan, katak wajib melompat sekali ke kanan dan akhirnya kembali ke tempat semula namun telah menggunakan energi. Jadi disini katak akan melompat ke kanan terus menerus sampai balok ke 10 dengan menggunakan energi .

= (6-8)^2 + (8-3)^2 + (3-5)^2 + (5-6)^2 + (6-4)^2 + (4-7)^2 + (7-10)^2 + (10-8)^2 + (8-11)^2

= 4 + 25 + 4 + 1 + 4 + 9 + 9 + 4 + 9 

= 69

B4.2. 10

Untuk soal ini, kita bisa tinggal mencoba setiap kemungkinan saja. Perhatikan bahwa ketika berada di balok 7, katak tidak mungkin melompat ke kiri, hal ini dikarenakan dengan melompat sekali maupun 2 kali ke kiri, katak akan membuat jarak antara balok dia sekarang dengan balok lain di kanan menjadi lebih besar, sehingga untuk kembali akan membutuhkan energi yang jauh lebih besar daripada jika dia langsung melompat ke kanan diawal. 

Pertama kita coba jika katak melompat sekali ke kanan dari balok 7 ke balok 8 menggunakan (7-10)^2 = 9 energi. Setelah ini, katak bisa memilih antara menggunakan lompatan super untuk ke balok 10, atau menggunakan 2 lompatan biasa untuk ke balok 10. Jika menggunakan lompatan super akan menggunakan 9 + 3 * (10-11)^2 = 12 energi, sedangkan dengan 2 lompatan biasa akan membutuhkan 9 + (10-8)^2 + (8-11)^2 = 22 energi.

Setelah ini kita coba jika katak melompat dua kali ke kanan dari balok 7 ke balok 9 menggunakan 3 * (7-8)^2 = 3 energi. Setelah itu, katak bisa antara lompat sekali ke kanan, atau lompat sekali ke kiri lalu menggunakan lompatan super untuk ke balok 10. Jika lompat sekali ke kanan akan menggunakan 3 + (8-11)^2 = 12 energi, sedangkan dengan lompatan biasa ke kiri kemudian lompatan super ke kanan akan menggunakan 3 + (10-8)^2 + 3 * (10-11)^2 = 10 energi. Jadi didapatkan energi minimum yang diperlukan yaitu 10

Soal Pemrograman Subsoal 1

Untuk mengerjakan subsoal 1, kita bisa menggunakan DP 2 state, dimana state pertama menyimpan posisi katak sekarang, dan state kedua untuk menyimpan saat ini katak telah melompat berapa kali. Meskipun sebenarnya katak bisa melompat terus menerus tanpa henti, pada jawaban optimal, katak pastinya tidak akan mengunjungi balok yang sama 2 kali, jadi kita sebenarnya hanya perlu mengecek N lompatan pertama saja, jika sudah melompat lebih dari itu, dapat dipastikan bahwa jawaban tersebut sudah tidak mungkin optimal. Untuk jawaban yang sudah tidak mungkin optimal, kita bisa membuat jawaban untuk DP di bagian itu dengan angka yang besar agar tidak mungkin diambil.

Kompleksitas: O(N^2)

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll solve(int n, vector<int> &tinggi, vector<vector<ll>> &dp, int posisi, int lompatan){

   if (posisi == n) return 0;

   if (lompatan == n) return 1e13;

   if (dp[posisi][lompatan] != -1) return dp[posisi][lompatan];

   ll harga = pow(tinggi[posisi] - tinggi[posisi + 1], 2);

   ll energi = solve(n, tinggi, dp, posisi + 1, lompatan + 1) + harga;

   if (posisi - 1 >= 1) {

       harga = pow(tinggi[posisi] - tinggi[posisi - 1], 2);

       energi = min(energi, solve(n, tinggi, dp, posisi - 1, lompatan + 1) + harga);

   }

   if (posisi - 2 >= 1){

       harga = pow(tinggi[posisi] - tinggi[posisi - 2], 2) * 3;

       energi = min(energi, solve(n, tinggi, dp, posisi - 2, lompatan + 1) + harga);

   }

   if (posisi + 2 <= n){

       harga = pow(tinggi[posisi] - tinggi[posisi + 2], 2) * 3;

       energi = min(energi, solve(n, tinggi, dp, posisi + 2, lompatan + 1) + harga);

   }

   return dp[posisi][lompatan] = energi;

}

int main(){

   int n;

   cin >> n;

   vector<int> tinggi(n + 1);

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

       cin >> tinggi[i];

   }

   vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, -1));

   cout << solve(n, tinggi, dp, 1, 0) << "\n";

   return 0;

}

Soal Pemrograman Subsoal 2

Perhatikan bahwa seperti yang dijelaskan pada B4.3, soal ini bisa diubah menjadi sebuah soal dijkstra biasa dimana balok merupakan node dan kedua lompatan merupakan edge dengan weight dari edgenya. Untuk soal pemrograman, hal yang sama bisa dilakukan juga, kita dapat mengubah input dari soalnya agar menjadi sebuah graf, dan kemudian melakukan algoritma dijkstra biasa dari balok 1 untuk mendapatkan jawaban optimalnya

Kompleksitas: O(N log N)

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main(){

   int n;

   cin >> n;

   vector<int> tinggi(n + 1);

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

       cin >> tinggi[i];

   }

   vector<vector<pair<int, ll>>> graf(n + 1);

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

       if (i - 1 >= 1) {

           ll energi = pow(tinggi[i] - tinggi[i - 1], 2);

           graf[i].push_back({i - 1, energi});

       }

       if (i - 2 >= 1){

           ll energi = pow(tinggi[i] - tinggi[i - 2], 2) * 3;

           graf[i].push_back({i - 2, energi});

       }

       if (i + 2 <= n){

           ll energi = pow(tinggi[i] - tinggi[i + 2], 2) * 3;

           graf[i].push_back({i + 2, energi});

       }

       if (i + 1 <= n){

           ll energi = pow(tinggi[i] - tinggi[i + 1], 2);

           graf[i].push_back({i + 1, energi});

       }

   }

   vector<ll> hargaMinimum(n + 1, -1);

   priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

   pq.push({0, 1});

   while(!pq.empty()){

       ll energi = pq.top().first, posisi = pq.top().second;

       pq.pop();

       if (hargaMinimum[posisi] != -1) continue;

       hargaMinimum[posisi] = energi;

       if (posisi == n) break;

       for (auto &balok : graf[posisi]){

           if (hargaMinimum[balok.first] != -1) continue;

           pq.push({energi + balok.second, balok.first});

       }

   }

   cout << hargaMinimum[n] << "\n";

   return 0;

}

Studi Kasus B5: Pencarian Strain Berbahaya Besar

B5.2. 10

Karena bentuk grafnya merupakan sebuah tree, dan sebuah jalur penularan harus berhenti di leaf(node yang tidak ada childnya lagi), pertanyaan ini sama saja dengan bertanya terdapat berapa leaf pada tree dengan rootnya A. Disini dapat dilihat terdapat 10 leaf yaitu 8, 11, 13, 14, 15, 16, 17, 18, 19, dan 20.

B5.3. 16

Untuk mendapatkan tingkat keganasannya, kita bisa mencari maksimum saja dari ke 10 jalur yang ada yaitu

1,3,7,13    = 6+4+3+1 = 14

1,3,7,14    = 6+4+3+2 = 15

1,3,8           = 6+4+6       = 16

1,4,9,15    = 6+3+2+4 = 15

1,4,9,16    = 6+3+2+3 = 14

2,5,10,17 = 2+4+3+4 = 13

2,5,10,18 = 2+4+3+1 =10

2,6,11        = 2+3+8       =13

2,6,12,19 = 2+3+3+4 = 12

2,6,12,20 = 2+3+3+5 = 13

Dari perhitungan dapat dilihat bahwa skor maksimum yaitu 16

Soal Pemrograman Subsoal 1

Untuk mendapatkan jawabannya, kita bisa looping saja mulai dari setiap virus dan pasien yang mereka infeksi. Dari situ, untuk setiap pasien saat ini, kita bisa looping semua data untuk mencari pasien lain yang akan terinfeksi oleh pasien saat ini.

Kompleksitas: O(N^2)

#include<bits/stdc++.h>

using namespace std;

int solve(vector<pair<int, int>> &pasien, vector<int> &waktuInap, int posisi){

   int keganasan = 0;

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

       if (pasien[i].first == posisi){

           keganasan = max(keganasan, solve(pasien, waktuInap, pasien[i].second));

       }

   }

   return keganasan + waktuInap[posisi];

}

int main(){

   int n, s, p;

   cin >> n >> s >> p;

   vector<int> waktuInap(n + 1);

   for (int i = 1; i <= n; i++) cin >> waktuInap[i];

   vector<pair<string, int>> virus(p);

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

       string nama;

       int k;

       cin >> nama >> k;

       virus[i] = {nama, k};

   }

   vector<pair<int, int>> pasien(n - p);

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

       int u, v;

       cin >> u >> v;

       pasien[i] = {u, v};

   }

   string namaVirus;

   int keganasanMaksimal = 0;

   for (auto &mulai : virus){

       int keganasan = solve(pasien, waktuInap, mulai.second);

       if (keganasan > keganasanMaksimal){

           keganasanMaksimal = keganasan;

           namaVirus = mulai.first;

       }

   }

   cout << namaVirus << "\n";

   cout << keganasanMaksimal << "\n";

   return 0;

}

Soal Pemrograman Subsoal 2

Perhatikan bahwa kita sebenarnya tidak perlu mengecek keseluruhan data untuk mencari pasien mana saja yang akan diinfeksi oleh pasien saat ini. Untuk menyimpan data tersebut kita bisa menggunakan adjacency list saja, untuk cara mendapatkan solusinya sendiri tidak berbeda jauh,  kita bisa menyelesaikan soal ini dengan melakukan DFS(Depth First Search) dari setiap virus yang ada. Dimulai dari root, kita tinggal mencoba semua child yang ada dari node tersebut sampai leaf dari setiap node, dari traversal ini kita akan mendapatkan tingkat keganasan dari setiap virus dan dapat langsung mengambil tingkat keganasan maksimal.

Kompleksitas: O(N)

#include<bits/stdc++.h>

using namespace std;

int solve(vector<vector<int>> &graf, vector<int> &waktuInap, int posisi){

   int keganasan = 0;

   for (auto &pasien : graf[posisi]){

       keganasan = max(keganasan, solve(graf, waktuInap, pasien));

   }

   return keganasan + waktuInap[posisi];

}

int main(){

   int n, s, p;

   cin >> n >> s >> p;

   vector<int> waktuInap(n + 1);

   for (int i = 1; i <= n; i++) cin >> waktuInap[i];

   vector<pair<string, int>> virus(p);

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

       string nama;

       int k;

       cin >> nama >> k;

       virus[i] = {nama, k};

   }

   vector<vector<int>> graf(n + 1);

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

       int u, v;

       cin >> u >> v;

       graf[u].push_back(v);

   }

   string namaVirus;

   int keganasanMaksimal = 0;

   for (auto &mulai : virus){

       int keganasan = solve(graf, waktuInap, mulai.second);

       if (keganasan > keganasanMaksimal){

           keganasanMaksimal = keganasan;

           namaVirus = mulai.first;

       }

   }

   cout << namaVirus << "\n";

   cout << keganasanMaksimal << "\n";

   return 0;

}

Studi Kasus B6: Mewarnai Kanvas

B6.1. 243

Karena setiap stiker mempunya ukuran 1x1, maka kita dapat dengan bebas mewarnai kanvas dengan warna apa saja, tidak terdapat kumpulan warna yang mustahil untuk didapatkan. Maka untuk setiap kotak, bebas untuk kita memilih salah satu dari 3 warna yang ada, jadinya akan terdapat 3 * 3 * 3 * 3 * 3 = 3^5 = 243 kemungkinan kanvas yang berbeda.

B6.2. 0

Perhatikan bahwa bagaimanapun cara kita memilih urutan dan cara meletakkan stiker, untuk stiker terakhir yang kita letakkan, pasti akan mengambil setidaknya 1x3 posisi berurutan. Dengan kata lain bagaimanapun cara kita memilih urutan stiker, pasti setidaknya akan terdapat 3 petak berturut-turut dengan warna yang sama, jadi tidak ada jawaban yang memenuhi syarat maksimal 2 petak berutur-turut dengan warna yang sama.

B6.3. 15

Untuk mendapatkan bentuk akhir dimana terdapat minimal 4 petak berturut-turut dengan warna yang sama, petak yang warnanya boleh berbeda hanyalah petak di awal atau petak di akhir, dan 3 petak ditengah wajib berwarna sama. Misal petak yang berwarna beda merupakan petak di akhir, berarti terdapat 2 kemungkinan warna, begitu juga jika petak yang berbeda berada di awal, juga terdapat 2 kemungkinan warna, dan yang terakhir jika kelima petak semua mempunyai warna yang sama, jadi disini total terdapat 5 kemungkinan berbeda. Namun, ini baru memperhitungkan kemungkinan dimana keempat petak diwarnai dengan 1 jenis warna saja, karena terdapat 3 jenis warna yang dapat digunakan, jawaban akhir yang benar adalah terdapat 5 * 3 = 15 kemungkinan berbeda. Untuk ke 15 kemungkinan yaitu sebagai berikut

H H H H H         B B B B B                K K K K K

H H H H B B B B B H K K K K H

H H H H K B B B B K K K K K B

B H H H H H B B B B H K K K K

K H H H H K B B B B B K K K K

Soal Pemrograman Subsoal 1

Agar suatu hasil akhir kanvas benar, harus terdapat minimal k petak berturut-turut dengan warna yang sama, karena untuk meletakkan stiker terakhir, pasti akan mengambil k buah petak. Untuk semua kombinasi lain dapat dibentuk asalkan syarat tersebut terpenuhi. Daripada mencari jumlah kombinasi yang mungkin, kita bisa membalikkan pertanyaannya dan mencari jumlah kombinasi yang tidak mungkin. Kita bisa membuat DP 2 state, state pertama menyimpan posisi saat ini, dan state kedua menyimpan sudah terdapat berapa petak berturut-turut yang berwarna sama. Jika jumlah petak yang berwarna sama sudah sama dengan k - 1, maka transisi ke posisi berikutnya hanya bisa menggunakan warna lain. Namun jika belum, maka kita bisa lanjut menggunakan warna yang sama maupun warna yang berbeda. Untuk mendapatkan jawaban akhir, kita bisa mencari semua kemungkinan kanvas berbeda dikurang dengan jumlah kemungkinan kanvas yang tidak mungkin

Kompleksitas: O(N * K)

#include<bits/stdc++.h>

#define ll long long

#define MOD 1000000007

using namespace std;

ll power(ll a, ll b){

   if (b == 0) return 1;

   ll res = power(a, b / 2);

   if (b % 2 == 1) return res * res % MOD * a % MOD;

   return res * res % MOD;

}

ll solve(int n, int m, int k, vector<vector<ll>> &dp, int posisi, int jumlahSama){

   if (posisi >= n) return 1;

   if (dp[posisi][jumlahSama] != -1) return dp[posisi][jumlahSama];

   if (jumlahSama == k - 1){

       return dp[posisi][jumlahSama] = solve(n, m, k, dp, posisi + 1, 1) * (m - 1) % MOD;

   }

   ll lanjut = solve(n, m, k, dp, posisi + 1, jumlahSama + 1);

   ll ulang = solve(n, m, k, dp, posisi + 1, 1) * (m - 1) % MOD;

   return dp[posisi][jumlahSama] = (lanjut + ulang) % MOD;

}

int main(){

   int n, m, k;

   cin >> n >> m >> k;

   if (k == 1){

       cout << power(m, n) << "\n";

       return 0;

   }

   vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -1));

   ll total = power(m, n);

   total -= (solve(n, m, k, dp, 1, 1) * m) % MOD;

   total += MOD;

   total %= MOD;

   cout << total << "\n";

   return 0;

}

Soal Pemrograman Subsoal 2

Disini kita akan tetap menggunakan DP 2 state, namun bedanya, state pertama akan menyimpan posisi saat ini, dan state kedua akan menyimpan 2 nilai, yaitu jumlah kombinasi berbeda yang belum terdapat k petak berturut-turut dengan warna yang sama, dan jumlah kombinasi berbeda yang sudah terdapat k petak berturut-turut dengan warna yang sama. 

Untuk index < k, nilai DP[i][0] = m^i dan DP[i][1] = 0. Hal ini karena jika posisi belum sampai k, kombinasi apapun tidak akan punya k petak berturut-turut dengan warna yang sama. 

Untuk ketika i == k, maka nilai DP[i][0] = m^k - m, sedangkan DP[i][1] = m, karena agar jumlah petak berturut-turut dengan warna yang sama bernilai k, hanya terdapat m kemungkinan, yaitu warnanya sama semua untuk setiap m warna berbeda. 

Kemudian untuk i > k, untuk DP[i][1] = DP[i - 1][1] * m, karena jika sudah terdapat k petak berturut-turut dengan warna yang sama, kita bisa tambahkan warna apapun dan hasilnya akan tetap sama. Untuk DP[i][0], pasti akan ada kombinasi yang akan perlu dipindahkan ke DP[i][1]. Ketika kita menghitung nilai untuk DP[i][0], jika kita menggunakan DP[i-1][0] * m, pasti akan terdapat beberapa kombinasi yang harusnya dipindahkan ke DP[i][1] karena sudah mencapai petak berturut-turut >= k, namun jika kita menggunakan DP[i-1][0] * (m-1) untuk memastikan kombinasinya tidak mencapai >= k, pasti ada beberapa kombinasi yang belum dimasukkan, dengan melakukan DP[i-1][0] * (m-1), semua nilai pada DP[i][0] akan berisi kombinasi dimana jumlah petak dengan nilai yang sama = 1, bagaimana dengan kombinasi dengan jumlah petak dengan nilai yang sama = 2, 3, 4, ..., k - 1? Itu dapat kita hitung menggunakan DP[i-2][0], DP[i-3][0], DP[i-4][0], ..., DP[i-(k-1)][0]. Jika nilai DP[i-1][0] * (m - 1) ditambah dengan DP[i-2][0] * (m - 1), maka kita sudah mendapatkan semua kombinasi dimana jumlah petak dengan nilai yang sama = 2, sama juga dengan DP[i-3][0] * (m - 1).

Sekarang untuk nilai DP[i][0] dapat dicari dengan (DP[i-1][0] + DP[i-2][0] + DP[i-3][0] + ... + DP[i-(k-1)][0]) * (m - 1). Untuk jumlah yang dipindahkan ke DP[i][1] sendiri dapat dihitung dengan DP[i-1][0] * m - DP[i][0]. Namun sekarang terdapat 1 masalah baru, yaitu untuk mencari nilai DP[i-1][0], DP[i-2][0] dst memerlukan waktu O(K). Untuk mempercepat ini, kita bisa membuat prefix sum untuk mencari nilainya dalam O(1).

Kompleksitas: O(N)

#include<bits/stdc++.h>

#define ll long long

#define MOD 1000000007

using namespace std;

ll power(ll a, ll b){

   if (b == 0) return 1;

   ll res = power(a, b / 2);

   if (b % 2 == 1) return res * res % MOD * a % MOD;

   return res * res % MOD;

}

int main(){

   int n, m, k;

   cin >> n >> m >> k;

   if (k == 1){

       cout << power(m, n) << "\n";

       return 0;

   }

   else if (k == n){

       cout << m << "\n";

       return 0;

   }

   vector<vector<ll>> dp(n + 1, vector<ll>(2, 0));

   vector<ll> prefix(n + 1, 0);

   dp[1][0] = m;

   dp[1][1] = 0;

   prefix[1] = m;

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

       dp[i][0] = dp[i - 1][0] * m % MOD;

       dp[i][1] = 0;

       prefix[i] = (prefix[i - 1] + dp[i][0]) % MOD;

   }

   dp[k][0] = (dp[k - 1][0] - 1) * m % MOD;

   dp[k][1] = m;

   prefix[k] = (prefix[k - 1] + dp[k][0]) % MOD;

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

       ll batasKanan = i - 1;

       ll batasKiri = i - k;

       dp[i][0] = (prefix[batasKanan] - prefix[batasKiri] + MOD) % MOD * (m - 1) % MOD;

       dp[i][1] = dp[i - 1][1] * m % MOD;

       dp[i][1] += (dp[i - 1][0] * m - dp[i][0]) % MOD;

       dp[i][1] %= MOD;

       prefix[batasKanan + 1] = (prefix[batasKanan] + dp[i][0]) % MOD;

   }

   cout << dp[n][1] << "\n";

   return 0;

}