# Pembahasan Simulasi 1
## A. Bos
### Pembahasan oleh Joel Gunawan
Perhatikan bahwa karena setiap bos gajinya harus lebih besar dari jumlah gaji bawahan langsungnya dan kita ingin meminimalisir jumlah gaji, maka kita gaji seorang bos adalah jumlah gaji semua bawahannya ditambah dengan $1$.

Perhatikan bahwa jika kita menambah sebuah pegawai baru, maka total gaji akan bertambah sebanyak banyak bos dari pegawai tersebut ke bos tertinggi ditambah satu.

Dengan observasi tersebut kita dapat dengan mudah mengetahui jumlah gaji yang perlu dikeluarkan jika orang $X$ menjadi root/bos tertinggi dengan syarat bahwa kita mengetahui jarak dari suatu karyawan ke karyawan lain. Oleh karena itu, kita dapat menghitung jarak dari setiap karyawan ke karyawan yang lain menggunakan *Breadth-First Search* (BFS) dari setiap karyawan.

Setelah mengetahui jumlah gaji yang perlu dikeluarkan jika orang $X$ menjadi root/bos tertinggi, maka kita cari yang minimal dari semua kemungkinan root/bos tertinggi.

Kompleksitas: $O(N(N+M))$

## B. Mesin
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Perhatikan bahwa dari angka 1, kita dapat melakukan operasi kali 2 ataupun tambah 3. Cobalah semua kemungkinan dan hentikan jika melebihi $N$, lalu keluarkan kemungkinan dengan perintah terpendek

Kompleksitas: $O(2^N)$
### Subsoal 3
Dari *brute force* di subsoal pertama, kita dapat mempercepat *brute force* dengan menggunakan *dynamic programming* (DP). Perhatikan bahwa jika kita dapat mencapai nilai $X$, maka kita cukup menyimpan yang paling optimal saja, tidak perlu semuanya. Oleh karena itu, kita akan membuat DP state dengan $DP[X] = \text{minimum operasi untuk mencapai nilai }X$. Transisi yang bisa dilakukan adalah dari operasi, yaitu mengali $2$ dan menambah $3$. Jika dibalik, maka kita bisa membagi $2$ dengan syarat bilangan genap atau mengurangi $3$.
Oleh karena itu, transisi DP yang kita lakukan adalah:
$DP[X] = \textit{min}(DP[X - 3], DP[X / 2])$ jika $X$ genap.
$DP[X] = DP[X - 3]$ jika $X$ ganjil.
Base case adalah kondisi awal, yaitu $DP[1] = 1$.
Kompleksitas: $O(N)$
### Solusi Penuh
Perhatikan bahwa untuk angka besar, akan lebih optimal jika kita membagi dengan 2 dibandingkan dengan mengurangi dengan 3. Oleh karena itu, kita dapat membagi dengan 2 terus hingga angka cukup kecil, lalu kita dapat selesaikan dengan menggunakan DP di subsoal sebelumnya.
Kompleksitas: $O(\text{log}N)$

## C. Mencari Pacar
### Pembahasan oleh Joel Gunawan
Karena dijamin bahwa terdapat suatu cara untuk pergi kencan tepat $N$ kali, maka kita dapat dengan mudah mencari suatu cara untuk pergi kencan tepat $N$ kali. Kita dapat menggunakan greedy dan memilih hari paling awal untuk pergi kencan hingga pergi $K$ kali.

Perhatikan bahwa dengan menggunakan algoritma ini kita dapat memeriksa apakah kita dapat pergi kencan lebih dari $K$ kali. Jika kita dapat pergi kencan $K + 1$ kali, maka jawaban pasti $-1$ karena kita dapat menghilangkan kencan manapun dari kencan dari konfigurasi $K + 1$ kali sehingga tidak ada hari di mana kita dapat pergi kencan.

Jika kencan maksimal yang bisa dijalani oleh Nesy adalah $K$ dengan menggunakan algoritma greedy di hari terawal, sebut saja hari-hari kencannnya adalah $T_1, T_2, ..., T_K$. Jika kita ingin menggeser hari kencan ke-$i$, maka pasti harus kita geser ke kanan. Untuk itu, kita coba menggeser $T_i, T_{i + 1}, ..., T_K$ sejauh mungkin ke kanan.

Perhatikan bahwa penggeseran ini sama saja melakukan algoritma greedy, tapi kita mulai dari belakang saja.

Dari situ, kita bisa simpulkan bahwa di sebuah hari kita harus pergi kencan jika hari tersebut ada di konfigurasi kencan dengan algoritma greedy dari hari paling awal dan algoritma greedy dari hari paling akhir.

Kompleksitas: $O(N)$ atau $O(N\textit{log}N)$ (tergantung implementasi).