# Pembahasan Simulasi 3

## A. Mira si Musang dan Pesawat
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Perhatikan bahwa jika kita mulai dari $1$ menuju ke $N$, maka hanya akan ada 1 titik saja yang maksimal. Awalnya, kita akan menaik terus ke ketinggian maksimal, lalu mempertahankan ketinggian, dan setelahnya menurun dari ketinggian maksimal.

Oleh karena itu, kita akan mencari maksimal dari $1 \ldots N$ lalu mencari minimal waktu yang dibutuhkan untuk mencapai ketinggian maksimal dan node yang dicapai saat mencapai ketinggian maksimal dari kiri dan dari kanan. Jika node ketinggian maksimal ada di $L, R$, maka nilai totalnya adalah $R - L + \text{cost}_L + \text{cost}_R$.

### Subsoal 2
Buatlah sebuah Dijkstra 2 state, state pertama adalah node dan state kedua adalah ketinggian. Detail implementasi Dijkstra diserahkan kepada pembaca.

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

### Subsoal 4
Kita mencoba melakukan Dijkstra dari titik awal dan titik akhir dan mencari minimum shortest path dari titik awal dan titik akhir ke setiap node dengan syarat minimal ketinggian dipenuhi.

Untuk pergi ke setiap node, kita akan menyimpan 2 hal yang penting untuk node tersebut. Pertama, simpan minimum waktu yang dibutuhkan untuk pergi ke tiap node (digabung dengan persyaratan ketinggian). Selain itu, kita akan menyimpan ketinggian maksimal yang dilewati untuk pergi ke sebuah node yang melewati ketinggian maksimum.

Kita akan mencoba untuk setiap node apabila dijadikan titik maksimum. Jika maksimum di node tersebut, maka kita cukup memeriksa apakah shortest path ke node tersebut maksimalnya adalah di node tersebut. Dengan kata lain, jika memeriksa node $x$, kita harus memeriksa apakah $max_\text{h dari 1} = max_\text{h dari n} = h_x$

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

## B. Padi Super
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Kita dapat mencoba untuk setiap sel di grid apakah titik tersebut termasuk ke dalam sel yang dipanen oleh Alien atau tidak.

Kompleksitas: $O(NMK)$

### Subsoal 2
Mengembangkan dari subsoal 1, kita perlu melakukan update setiap kali sel dipanen oleh Alien lalu untuk sel yang tidak dipanen maka kita akan tambah sebanyak 1.

Kompleksitas: $O(NMK)$

### Subsoal 3
Untuk subsoal ini, kita cukup memeriksa banyak sel yang dipanen oleh Alien. Untuk itu, kita akan mencari banyak sel ke kiri/kanan yang jaraknya kurang dari jarak yang ditentukan jika kita bergerak ke atas/bawah. Setiap kita bergerak sebanyak $x$ di sumbu vertikal (atas atau bawah), kita mencari tahu jarak terjauh kita bisa bergerak secara horizontal (kiri atau kanan). Hal ini bisa dicari menggunakan persamaan kuadrat dasar. Dari situ, kita bisa mencari total sel yang dipanen oleh Alien.

Kompleksitas: $O(NK)$

### Subsoal 4
Hal yang perlu dikembangkan dari subsoal sebelumnya adalah bagaimana cara menangani beberapa pemanenan Alien di suatu sel. Untuk menangani hal tersebut, kita cukup memeriksa waktu terakhir Alien memanen sebuah sel.

Untuk mencari waktu terakhir pemanenan Alien, kita dapat melakukan line sweep di tiap baris grid, memeriksa jumlah sel yang dipanen di akhir hari tertentu.

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

## C. Sandi Barisan
### Pembahasan oleh Joel Gunawan
### Subsoal 3
Perhatikan bahwa barisan yang valid adalah barisan yang nilainya naik dan turun secara bergantian.

Kita akan mencoba setiap kemungkinan baris sandi yang valid dengan menggunakan sebuah DP 3 state, yaitu $DP[pos][last][up/down] = \text{banyak cara}$.

Base case dari DP merupakan di posisi 1, dengan $DP[1][K][0] = DP[1][K][1] = 1$ karena dari posisi awal kita bisa meningkatkan atau menurunkan nilai.

Saat sebelumnya naik, maka nilai DP selanjutnya harus turun. Hal yang sama juga berlaku sebaliknya. Oleh karena itu, kita dapat membuat transisi berikut:
- $DP[pos][last][up] = DP[pos][last - i][down]$ untuk semua nilai $1 \le i < last$.
- $DP[pos][last][up] = DP[pos][last + i][down]$ untuk semua nilai $1 \le i < N - last$.

Kompleksitas: $O(N^3)$

### Subsoal 4
Kita dapat mempercepat transisi dengan menggunakan prefix/suffix sum pada DP yang kita hitung sehingga transisi akan berubah menjadi $O(1)$.

Kompleksitas: $O(N^2)$