# Pembahasan Simulasi 5
## A. Operasi Bersejarah
### Pembahasan oleh Joel Gunawan
Kita bisa mengartikan ulang apa yang diminta oleh soal ini. Perhatikan bahwa untuk sebuah penerbangan optimal hal-hal berikut akan berlaku:
- Tidak ada titik koordinat yang dilewati lebih dari satu kali.
- Teleportasi hanya terjadi di kota saja, tidak mungkin terjadi di antara dua kota.

Setiap naga sampai ke sebuah kota ada dua pilihan aksi yang bisa dilakukan, terbang ke kota lain sesuai dengan arahnya atau melakukan teleportasi.

Oleh karena itu, kita bisa menyederhanakan soal ini menjadi "Carilah banyak segmen minimum sehingga panjang total segmen $\le K$".

### Subsoal 1
Perhatikan bahwa segmen $[L, R]$ valid jika $S_L =$```R``` atau $S_R =$```L```. Dari situ, kita dapat simpulkan di subsoal ini bahwa setiap segmen valid.

Perhatikan bahwa dari situ kita dapat melakukan pencarian banyak segmen minimum dengan greedy. Awalnya, kita menganggap semuanya menjadi suatu segmen terlebih dahulu. Lalu, antara dua kota kita dapat memilih untuk menelusuri jarak antara kedua kota itu atau kita dapat meloncatinya saja menggunakan teleportasi.

Kita tinggal memilih jarak antarkota yang terbesar terus menerus hingga panjang segmen total $\le K$.

Kompleksitas: $O(N\text{log}N)$

### Subsoal 2
Kita dapat mencoba setiap kemungkinan "pemisah" antara segmen lalu memeriksa validitas masing-masing segmen. Banyak pemisah ada $N - 1$ (antara setiap kota).

Kompleksitas: $O(N2^N)$

### Subsoal 3
Perhatikan bahwa yang menjadi perbedaan antara subsoal 1 dan subsoal ini adalah kita harus memeriksa validitas dari sebuah segmen yang kita pisah, sehingga kita tidak boleh pisah secara sembarangan.

Oleh karena itu, kita dapat membuat sebuah $DP$ dengan state $DP[idx][teleport] = \text{minimum total panjang segmen}$.

Transisi $DP$ adalah sebagai berikut:
$DP[idx][teleport] = min(DP[j][teleport - 1] + panjang(j + 1, idx))$ dengan syarat $S_{j + 1} =$```R``` atau $S_R =$```L``` dan $j < idx$.

Perhatikan bahwa $panjang(j + 1, idx)$ dapat dihitung dengan mudah, yaitu $A_{idx} - A_{j + 1}$.

Kompleksitas: $O(N^3)$

### Subsoal 4
Perhatikan bahwa yang menjadikan solusi di subsoal sebelumnya lambat adalah transisi yang dilakukan memiliki kompleksitas $O(N)$ per state. Oleh karena itu, kita ingin mempercepat transisi $DP$.

Pertama kita coba jabarkan dulu rumus transisi $DP$ menjadi bentuk yang lebih lengkap.

$$DP[idx][teleport] = min(DP[j][teleport - 1] + A_{idx} - A_{j + 1})$$

Perhatikan bahwa di rumus tersebut kita dapat mengeluarkan suku-suku yang tidak berhubungan dengan $j$ dan rumus tersebut dapat diubah menjadi:

$$DP[idx][teleport] = A_{idx} + min(DP[j][teleport - 1] - A_{j + 1})$$

Pertama, kita akan bagi transisi $DP$ menjadi dua kasus yang berbeda:
1. $S_{idx} =$```L```, di kasus ini maka kita dapat memilih setiap nilai $j < idx$ untuk melakukan transisi.
2. $S_{idx} =$```R```, di kasus ini maka kita hanya dapat melakukan transisi dari setiap nilai $j < idx$ dimana $S_j =$```R```.

Perhatikan bahwa di kasus pertama kita ingin mencari nilai $DP[j][teleport - 1] - A_{j + 1}$ yang minimal untuk setiap $j$ yang lebih kecil. Oleh karena itu, untuk setiap nilai $teleport$ kita akan menyimpan prefiks minimum dari $DP[x][teleport] - A_{x + 1}$.

Hal yang serupa dapat kita lakukan untuk kasus kedua. Akan tetapi, kita hanya memasukkan semua indeks $x$ dimana $S_x =$```R``` saja ke dalam prefiks maksimumnya.

Kompleksitas: $O(N^2)$

## B. Mewarnai Kanvas
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Perhatikan apa yang terjadi jika kita menganggap penempelan terakhir akan terjadi di segmen $[i, i + K - 1]$ dan melakukan urutan penempelan sebagai berikut:


Perhatikan bahwa semua petak di luar $[i, i + K - 1]$ dapat merupakan warna apapun. Oleh karena itu, pewarnaan valid adalah pewarnaan dimana terdapat setidaknya sebuah $[i, i + K - 1]$ dimana warna semua petak di segmen tersebut sama. Dengan kata lain, terdapat sebuah segmen dengan panjang setidaknya $K$ dengan warna yang sama. Dapat dibuktikan bahwa ini adalah satu-satunya syarat.

Oleh karena itu, kita akan membuat sebuah $DP[idx][warna][wk][valid]$, dimana $idx$ menyatakan indeks sekarang dan $warna$ menandakan warna terakhir dan $wk$ menandakan berapa berturut-turut warna terakhir dan state terakhir menandakan apakah sudah terdapat setidaknya suatu segmen yang memiliki warna sama dengan panjang $K$.

Transisi $DP$ dapat dibagi menjadi 2 kasus:
- Warna yang dimasukkan ke petak sekarang sama dengan warna sebelumnya, $DP[idx][warna][wk][valid] = DP[idx - 1][warna][wk - 1][valid]$. Perhatikan bahwa jika $valid = 1$ dan $wk \ge K$, maka transisi $DP[idx][warna][wk][valid] = DP[idx - 1][warna][wk - 1][0]$ juga berlaku.
- Warna yang dimasukkan ke petak sekarang berbeda dengan warna sebelumnya, $DP[idx][warna][1][valid] = DP[idx - 1][warna2][wk][valid]$. Perhatikan bahwa $warna2 \neq warna$.

Dengan menggunakan kedua transisi tersebut, hasil akhirnya adalah jumlah semua $DP[N][warna][wk][1]$.

Kompleksitas: $O(N^3)$

### Subsoal 2
Perhatikan bahwa kita bisa mengubah soal ini menjadi "carilah banyaknya cara mewarnai sehingga tidak ada segmen $K$ konsekutif dengan warna sama". Untuk mencari itu kita bisa menggunakan $DP[idx]$ yang menyimpan banyak cara mewarnai hingga $idx$ dengan tidak ada $K$ konsekutif warna sama.

Karena itu, perhatikan bahwa untuk membuat pewarnaan valid, kita bisa menambah bagian belakang dari segmen yang sudah valid dengan sebuah segmen dengan warna yang berbeda dengan warna di belakang segmen valid asal panjangnya tidak sampai $K$. Dengan kata lain, jika warna segmen terakhir sebuah pewarnaan valid adalah $X$, maka kita dapat memasukkan sebuah segmen warna $Y$ yang panjangnya tidak sampai $K$ di belakang pewarnaan valid.

Oleh karena itu, kita dapat menyimpulkan bahwa transisi DP adalah sebagai berikut:
$DP[idx] = sum(DP[idx - i] \times (M - 1)), 1 \le i < K$. Kita mengali dengan $M - 1$ karena ada $M - 1$ warna yang tidak sama dengan warna di belakang segmen valid yang kita perpanjang.

Untuk melakukan transisi DP dengan cepat kita dapat menggunakan *prefix sum*.

Pertama, kita ubah transisi DP menjadi sebagai berikut.
$DP[idx] = sum(DP[idx - i]) \times (M - 1), 1 \le i < K$

Lalu kita mendefinisikan $pref[idx] = DP[1] + DP[2] + \ldots + DP[idx]$.

Kita dapat mengganti $sum(DP[idx - i])$ dengan $pref[idx - 1] - pref[idx - K]$. Dengan itu, transisi DP menjadi $O(1)$.

Jika kita bisa mencari pewarnaan yang tidak valid, maka untuk mencari pewarnaan yang valid cukup dengan inklusi-eksklusi saja. Banyak cara total adalah $M^N$. Oleh karena itu, jawaban akhir adalah $M^N - DP[N]$.

Kompleksitas: $O(N)$

## C. Max Adiksi
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Untuk subsoal ini, kita cukup memeriksa apakah satu tangan cukup untuk menekan semua nada. Jika tidak cukup, maka jawabannya adalah kita memerlukan dua tangan.

Perhatikan bahwa untuk memeriksa apakah bisa dengan satu tangan kita cukup memulai proses dari waktu terkecil hingga waktu terbesar. Untuk berpindah dari titik $i$ ke $j$ dengan $T_i \le T_j$, maka $T_j - T_i \ge |A_j - A_i|$ harus terpenuhi.

Kompleksitas: $O(N)$

### Subsoal 2
Untuk subsoal ini, kita harus bisa memeriksa apakah permasalahan bisa diselesaikan dengan dua tangan. Kita bisa membuat DP 3 state, $DP[idx][tangan1][tangan2] =$ posisi tangan 1 dan tangan 2 dengan menghitung $idx$ nada pertama. Perhatikan bahwa proses urutan nada harus diurutkan berdasarkan waktu.

Transisi DP dapat dilakukan dengan waktu $O(N)$ per state dan diserahkan kepada pembaca sebagai latihan.

Kompleksitas: $O(N^4)$

### Subsoal 3
Untuk subsoal ini, kita harus bisa memeriksa apakah permasalahan bisa diselesaikan dengan tiga tangan. Jika kita menggunakan cara berpikir yang sama dengan subsoal sebelumnya, maka kita akan membuat DP 4 state, $DP[idx][tangan1][tangan2][tangan3]$. Akan tetapi, perhatikan bahwa salah satu dari $tangan1$, $tangan2$, atau $tangan3$ pasti mempunyai nilai $idx - 1$. Oleh karena itu, kita bisa membuat DP 3 state sama seperti sebelumnya, yaitu $DP[idx][tangan1][tangan2]$. Akan tetapi, kita akan menyimpan posisi tangan yang berada di $idx - 1$ sebagai *implicit state*.

Dari situ, kita bisa mengurangi state $DP$ yang dibutuhkan menjadi $N^3$. Transisi DP bisa dilakukan dalam $O(N)$ per state. Untuk detilnya diserahkan kepada pembaca sebagai latihan.

Kompleksitas: $O(N^4)$

### Subsoal 5
Perhatikan bahwa jika kita memilih untuk mempunyai beberapa tangan, maka tidak akan pernah optimal untuk posisi kedua tangan tersebut bersilangan.


Jika tangan 1 menekan nada $A$ dan tangan 2 menekan nada $B$, maka dapat dipastikan bahwa paling optimal tangan 1 menekan nada $C$ dan tangan 2 menekan nada $D$.

Oleh karena itu, kita bisa memproses nada-nada dari paling kiri ke kanan (diurutkan berdasarkan $A$). Kita akan memulai untuk suatu tangan yang akan mencoba untuk menekan nada-nada paling kiri. Jika tangan tersebut tidak sempat untuk menekan sebuah nada, maka nada tersebut akan ditekan oleh tangan berikutnya.

Untuk memeriksa apakah sebuah tangan sempat untuk menekan nada dengan waktu $T$ dan posisi $A$, maka kita cukup memeriksa apakah kita sempat berpindah ke nada yang akan ditekan berikutnya/sebelumnya oleh tangan tersebut.

Kompleksitas: $O(N^2)$

### Subsoal 7
Perhatikan bahwa untuk setiap titik kita bisa mencari tangan yang digunakan untuk penekanan menggunakan *binary search*. Selain itu, untuk memasukkan nada yang ditekan suatu tangan dalam urutan yang benar kita bisa menggunakan struktur data seperti *set*.

Kompleksitas: $O(N\text{log}^2N)$