# Pembahasan Simulasi 2
## A. Kereta Mainan
### Pembahasan oleh Matthew Hutama Pramana
Abridged description
Carilah banyak jumlah yang mungkin ketika membuat sebuah array $A$ berukuran $M$ dengan syarat $(A_1 + 1) \times (A_2 + 1) \times ... \times (A_M + 1) = N$.
### Subsoal 1
Untuk subtask ini, kita dapat coba satu per satu kemungkinan $M$, banyak tipe mainan dan mencoba tiap kemungkinan $A_1$ hingga $A_M$. Perhatikan bahwa kita bisa berasumsi bahwa $A_i \ge A_{i + 1}$.
### Subsoal 2
Jelas nilai $A_i + 1$ adalah faktor dari $N$, dan maksimal banyak faktor dari sebuah bilangan yang kurang dari sama dengan $10 \, 000$ adalah $20$, sehingga untuk subsoal ini dapat kita bruteforce. Kita harus membuat brute force yang optimal sehingga kita hanya mengunjungi setiap kemungkinan tepat sekali. Oleh karena itu, kita dapat melakukan brute force dengan syarat bahwa bilangan yang kita pilih harus kurang dari atau sama dengan bilangan sebelumnya yang kita pilih di brute force.
### Subsoal 5 (Tanpa Batasan)
Perhatikan bahwa kita cukup memeriksa hasil perkalian yang merupakan faktor dari $N$. Misalkan $F$ merupakan array yang berisi semua faktor $N$. Maka kita cukup memeriksa jumlah yang mungkin dibuat dari masing-masing faktor.

Misalkan sebuah faktor $F_i$ bisa didapat dari perkalian faktor $F_j$ dan $F_k$ dimana $F_j$ , $F_k > 1$. Maka jika $F_j$ dapat dibentuk dengan $a$ mainan dan $F_k$ dapat dibentuk dengan $b$ mainan, maka $F_i$ dapat dibentuk dengan $a + b$ mainan.

Dengan menggunakan observasi tersebut, maka kita dapat melakukan DP 1 state dengan state tersebut merupakan faktor dari $N$ yang menyimpan semua kemungkinan nilai untuk $N$.

Perhatikan bahwa maksimum ada $\text{log}N \times \text{ans}$ perhitungan. Perhatikan bahwa upper bound jawaban kurang lebih proporsional dengan $\text{sqrt}(N)$ karena banyak faktor bertumbuh maksimal proporsional dengan $\text{sqrt}(N)$. Oleh karena itu, upper bound sekitar $10 \, 000$ hingga $100 \, 000$

## B. Toilet
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Karena batasan $M$ cukup kecil, kita bisa mencoba setiap gedung yang mungkin dan mencari berapa maksimal toilet yang bisa disewa jika berada di gedung $X$. Jika kita memilih setiap gedung $X$, maka kita dapat menghitung untuk setiap toilet berapa harga yang perlu kita keluarkan untuk menyewa toilet tersebut.

Jika anggaran maksimal kita adalah $R$, maka kita bisa menggunakan teknik *greedy* untuk mencari banyak toilet maksimum yang bisa disewa. Kita akan memilih untuk menyewa toilet dengan harga terkecil terlebih dahulu. Kita perlu mencari harga toilet terkecil sebanyak $N$ kali dan setiap pencarian membutuhkan $N$ operasi. Banyak gedung yang dicoba adalah $M$. Oleh karena itu, didapat kompleksitas $O(N^2M)$.

Kompleksitas: $O(N^2M)$

### Subsoal 2
Perhatikan bahwa pencarian toilet dengan harga terkecil dapat dilakukan dengan lebih cepat. Jika di setiap posisi gedung kita mengurutkan harga toilet terkecil ke terbesar, maka kita cukup mencoba untuk menyewa toilet mulai dari harga terkecil sampai tidak bisa lagi dengan menggunakan *for loop* biasa saja. Oleh karena itu, kompleksitas bisa dikurangi dari $N^2$ menjadi $N\text{log}N$.

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

### Subsoal 3 (Solusi 1)
Dapat dilihat bahwa salah satu gedung yang mampu menyewa toilet paling banyak adalah gedung yang memiliki toilet. Perhatikan bahwa jika kita memilih suatu gedung $X$ yang tidak memiliki toilet.

Misalnya, kita memilih tinggal di suatu gedung $X$ dan kita memilih suatu kumpulan toilet untuk disewa. Ada $L$ toilet di kiri gedung $X$ dan ada $R$ toilet di kanan gedung $X$. Jika ada toilet di gedung $X$ anggap saja bisa masuk $L$ ataupun $R$. Berikut adalah beberapa kasus yang mungkin:

- $L > R$, di kasus ini, jika kita pindah ke gedung $X-1$ maka harga yang dibutuhkan untuk menyewa akan lebih murah sehingga bisa saja kita menyewa toilet lain lagi dari uang yang kita hemat.
- $L < R$, di kasus ini, jika kita pindah ke gedung $X+1$ maka harga yang dibutuhkan untuk menyewa akan lebih murah sehingga bisa saja kita menyewa toilet lain lagi dari uang yang kita hemat.
- $L = R$, di kasus ini, jika kita pindah ke gedung $X + 1$ atau ke gedung $X-1$ tidak berubah atau bisa jadi menambah.

Oleh karena itu, tempat pemilihan gedung akan optimal jika $L = R$.

Perhatikan bahwa jika kita memilih suatu kumpulan toilet sembarang, kasus $L = R$ pasti bisa terjadi di suatu gedung yang memiliki toilet jika kita mengatur toilet di gedung $X$ sedemikian rupa sehingga hal tersebut terjadi.

Karena kita cukup mencoba posisi gedung dimana ada toilet saja, maka paling banyak ada $N$ gedung yang mempunyai toilet. Oleh karena itu, solusi yang kita buat di subsoal sebelumnya dapat digunakan tetapi dengan mengurangi pencobaan posisi gedung dari $M$ menjadi $N$.

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

### Subsoal 3 (Solusi 2)
Untuk setiap posisi gedung yang dicoba, perhatikan bahwa kita pasti akan selalu memilih toilet dengan harga minimal untuk disewa. Untuk menghabiskan anggaran $R$ pasti ada suatu angka $X$ dimana kita akan menyewa toilet dengan harga paling tinggi $X$ saja.

Untuk meminimalisir banyak toilet yang tidak disewa ketika kit memilih $X$, maka kita bisa mencari nilai $X$ terkecil dengan menggunakan [*binary search the answer*](https://cp-algorithms.com/num_methods/binary_search.html). Jika kita memilih $X$ minimal, maka toilet yang bisa jadi tidak disewa hanyalah toilet dengan harga $X$ saja.

Kita bisa memeriksa jumlah jarak dari suatu elemen menuju semua elemen yang berada di segmen $[L, R]$ dengan menggunakan [*prefix sum*](https://usaco.guide/silver/prefix-sums?lang=cpp).

Kita akan membuat 2 *prefix sum*. *Prefix sum* pertama, sebut saja $A$ akan menymipan banyak elemen di setiap titik. *Prefix sum* kedua, sebut saja $B$ akan menyimpan jumlah dari posisi toilet. Contohnya, jika ada toilet di posisi $2, 4, 4, 5, 7, 9$ secara berturut-turut maka *prefix sum* $A$ dan $B$ akan berisi sebagai berikut:

| $\text{index}$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $A$ | $0$ | $0$ | $1$ | $1$ | $3$ | $4$ | $4$ | $5$ | $5$ | $6$ |
| $B$ | $0$ | $0$ | $2$ | $2$ | $10$ | $15$ | $15$ | $22$ | $22$ | $31$ |

Menggunakan kedua *prefix sum* ini, kita bisa mencari jarak dari suatu titik $X$ ke semua toilet di $[L, X]$ ataupun $[X, R]$.
- Untuk kasus $[L, X]$, jumlah semua jarak bisa didapatkan dengan rumus $(A_X - A_{L-1}) \times X - (B_X - B_{L-1})$.
- Untuk kasus $[X, R]$, jumlah semua jarak bisa didapatkan dengan rumus $(B_R - B_{X - 1}) - ((A_R - A_{X - 1}) \times X)$

Dengan itu, kita bisa menghitung biaya yang diperlukan untuk menyewa toilet di range $[L, R]$ jika dipusatkan di suatu gedung $X$ dalam $O(1)$. Oleh karena itu, *binary search the answer* akan berjalan dalam $O(1) \times O(\text{log}M) = O(\text{log}M)$ operasi.

Karena kita memeriksa setiap posisi, maka total kompleksitasnya adalah $O(M\text{log}M)$.

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

### Subsoal 4
Untuk solusi penuh, kita bisa menggabungkan kedua solusi yang mungkin untuk subsoal 3. Kita akan menggunakan teknik $O(\text{log}M)$ untuk memeriksa setiap gedung dan hanya memeriksa gedung yang mengandung toilet saja, yaitu maksimal sebanyak $N$.

Akan tetapi, yang menjadi masalah adalah bagaimana cara kita menyimpan *prefix sum* karena batasan $M$ bisa sampai dengan $10^9$. Perhatikan bahwa indeks yang penting di *prefix sum* hanyalah indeks yang berubah saja, yaitu gedung yang mengandung toilet. Oleh karena itu, kita cukup menyimpan paling banyak $N$ posisi penting di *prefix sum* yang bisa dilakukan dengan teknik [*coordinate compression*](https://usaco.guide/silver/sorting-custom?lang=cpp).

Contohnya *prefix sum* $A$ dan $B$ (lihat subsoal 3 solusi 2) akan berisi sebagai berikut:

| $\text{index}$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
| --- | --- | --- | --- | --- | --- | --- |
| $\text{pos}$ | $0$ | $2$ | $4$ | $5$ | $7$ | $9$ |
| $A$ | $0$ | $1$ | $3$ | $4$ | $5$ | $6$ |
| $B$ | $0$ | $2$ | $10$ | $15$ | $22$ | $31$ |

$\text{pos}$ merupakan indeks di *prefix sum* jika sama seperti di subsoal sebelumnya.

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

## C. Mencari Teman
### Pembahasan oleh Joel Gunawan
### Subsoal 1
Kita akan melakukan brute force setiap penembakkan portal yang mungkin. Kita akan membuat dijkstra dengan 3 state, yaitu: posisi sekarang, portal 1, dan portal 2. Di tiap posisi kita dapat mengubah portal yang ditembakkan dengan portal baru yang berada di kanan, atas, bawah, ataupun kiri dari sel tempat kita berada. Ini dapat di hitung terlebih dahulu dengan kompleksitas $O(NM(N+M))$ dengan mudah. Transisi Dijkstra diserahkan kepada pembaca sebagai latihan.

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

### Subsoal 2
Perhatikan bahwa ketika kita pergi ke suatu portal, kita perlu masuk ke portal lain yang ada di tembok juga. Oleh karena itu, kita cukup menyimpan 1 portal saja, portal yang akan kita tuju. Portal yang kita masuki dapat dibuat ketika kita sedang berada di tembok saja.

Solusi sama seperti dengan subsoal sebelumnya tetapi state portal dikurangi 1, sehingga menjadi posisi sekarang dan posisi portal.

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

### Subsoal 3
Perhatikan bahwa ketika kita menembakkan sebuah portal, cara paling optimal adalah dengan menuju ke portal itu secara langsung melewati sebuah portal lain. Perhatikan jika kita menembakkan sebuah portal ke manapun, dijamin di sel yang kita tempati bahwa kita ada di sebelah tembok. Oleh karena itu, kita bisa menembakkan portal ke tembok yang bersebelahan dengan sel sekarang dan kita bisa langsung menggunakan portal di sel sekarang untuk menuju ke portal lain yang kita tembakkan. Dari situ, kita bisa buat soal ini menjadi BFS (*Breadth-First Search*) biasa saja dengan tambahan edge yang menggunakan portal dengan kompleksitas $O(NM)$. Ingat bahwa perhitungan sel mana portal akan ditembakkan mempunyai kompleksitas $O(NM(N+M))$ yang tetap lolos di subsoal ini.

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

### Subsoal 4
Hal yang berbeda dibandingkan dengan subsoal sebelumnya adalah kita harus mencari di mana letak tembok terdekat dari setiap sel. Untuk mencari itu, kita bisa melakukan [*multisource* BFS](https://www.geeksforgeeks.org/multi-source-shortest-path-in-unweighted-graph/), yaitu BFS yang dimulai dari beberapa node secara sekaligus. Kita akan melakukan *multisource* BFS dari setiap sel yang bersebelahan dengan tembok. Dari setiap sel, ketika kita menembakkan portal maka kita akan langsung menuju tembok terdekat lalu menuju ke portal yang kita tembakkan melewati portal di tembok terdekat. *Multisource* BFS ini bisa dilakukan dengan kompleksitas $O(NM)$ total.

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

### Subsoal 5
Perhatikan bahwa hal yang membuat perhitungan sebelumnya lambat adalah mencari tembok yang ada tepat di kiri/kanan/atas/bawah dari setiap sel. Hal ini bisa kita komputasi dengan mulai dari tembok saja. Kita bisa mengiterasi dari setiap tembok $X$ menuju ke setiap arah sampai kita menemukan tembok lain. Nanti kita bisa menyimpan untuk tiap sel bahwa tembok $X$ merupakan tembok terdekat di salah satu arahnya.

Contohnya, jika ada sel $Y$ yang di kanan dari tembok $X$ dan tidak ada tembok antara $X$ dan $Y$, maka jika dari posisi $Y$ kita menembakkan portal ke kiri, maka portal akan terbuka di tembok $X$.

Oleh karena itu, perhitungan bisa dipercepat menjadi $O(NM)$.

Kompleksitas: $O(NM)$