# Pembahasan Simulasi 4
## A. Permainan Mengerikan
### Pembahasan oleh Joel Gunawan
### Subsoal 2
Coba DFS di setiap pulau sebagai titik awal untuk sebuah nilai undian $X$ lalu pergi ke semua pulau yang bisa dituju dengan DFS dengan syarat nilai undian tersebut.

Kompleksitas: $O(N^3)$.

### Subsoal 4
Perhatikan untuk subsoal ini kita dapat mencoba untuk setiap nilai undian, kita akan melakukan [*disjoint set union*](https://cp-algorithms.com/data_structures/disjoint_set_union.html) (DSU) menggunakan jembatan-jembatan yang nilainya lebih dari nilai undian yang kita coba. Dari pulau-pulau yang digabung dengan DSU, kita bisa mengetahui jumlah nilai dari sebuah pulau-pulau yang tergabung.

### Subsoal 5
Kita dapat mengoptimisasi solusi di subsoal 4. Perhatikan bahwa untuk DSU di nilai undian $x$, maka semua edge yang digunakan dalam DSU di nilai undian yang $\ge x$. Oleh karena itu, kita cukup menambahkan edge baru terhadap DSU sehingga edge-edge lama tidak perlu di *merge* ulang lagi.

## B. Cari Inversi Sepenuhnya
### Pembahasan Asli oleh Pikatan Arya Bramajati (diterjemahkan oleh Joel Gunawan)
Pembahasan asli soal dapat dilihat [disini](https://tlx.toki.id/problems/compfest-15-jcpc-penyisihan/C)

Perhatikan bahwa selama proses dijalankan, setiap kali kiat melakukan ```dfs(x)``` untuk sebuah nilai $x$ yang sama, maka nilai yang ditambahkan kepada $Z$ selalu sama. Oleh karena itu, unutk setiap verteks $x$, kita mau mendapatkan sebuah properti tentang urutan nilai yang akan ditambahkan jika kita melakukan ```dfs(x)```. Karena kita mau menghitung banyak inversi di sebuah barisan yang terdiri dari $0$ atau $1$ saja, untuk setiap $x$, kita mau menghitung:
- $f_0[x]:$ banyk elemen $0$ yang ditambahkan di akhir.
- $f_1[x]:$ banyak elemen $1$ yang ditambahkan di akhir.
- $\text{inv}[x]:$ banyak inversi di dalam barisan yang ditambahkan.

Setelah itu, kita bisa menyelesaikan masalah menggunakan *dynamic programming* pada *directed acyclic graph*. Untuk setiap $x$, kita meng-*iterasi* verteks $y$ yang dapat dituju dari $x$ (mengikuti urutan yang diberikan di masukan). Jika bilangan bulat di *edge* yang dilalui adalah $w$, maka kita akan menambahkan $f_w[y]$ dengan $1$ untuk sementara dan jika $w = 1$ kita akan menambahkan $\text{inv}[y]$ dengan $f_0[y]$ untuk sementara. Setelah itu, kita dapat melakukan transisi berikut:
- Tambahkan $\text{inv}[x]$ dengan $\text{inv}[y] + f_1(x) \times f_0(y)$.
- Tambahkan $f_0[x]$ dengan $f_0[y]$.
- Tambahkan $f_1[x]$ dengan $f_1[y]$.

Jawaban untuk soal ini adalah $\text{inv}[1]$.

Kompleksitas: $O(N + \sum S)$

## C. Perayaan Ulang Tahun
### Pembahasan oleh Audra Aurora Izzani

### Subsoal 1

Karena nilai $N$ yang kecil, kita dapat mencari luas dari semua potongan kue yang mungkin. Gunakan shoelace algorithm untuk mencari luasnya.

Kompleksitas waktu: $O(N^3)$

### Subsoal 2

Perhatikan bahwa potongan kue dengan area terkecil pasti berupa segitiga. Selain itu, di kue ini, potongan kue segitiga hanya bisa dibentuk oleh tiga titik berurutan. The proof is left to the reader as an exercise :)

Kompleksitas waktu: $O(N^2)$

### Subsoal 3

Kita dapat merepresentasikan sebuah potongan kue dengan pasangan titik tempat kue dipotong. Untuk membedakan kedua potong kue, kita bisa memanfaatkan perbedaan urutan pasangan (contoh: searah jarum jam bila index titik pertama lebih kecil, berlawanan arah jarum jam bila index titik pertama lebih besar).

Karena kita hanya butuh potongan kue terkecil ke-$U$, kita hanya perlu mencari potongan kue terkecil pertama sampai ke-$U$. Dalam kata lain, jika kita sudah menemukan $U$ potongan kue terkecil sementara dan kita menemukan potongan kue yang lebih kecil daripada potongan kue terkecil ke-$U$ sementara, kita harus membuang potongan kue terkecil ke-$U$ sementara dan memasukkan potongan kue yang lebih kecil. Untuk melakukan ini, kita dapat menyimpan luas kue terkecil pertama sampai ke-$U$ sementara di priority queue.

Belajar dari Subsoal 2, kita pertama mencari luas dari segitiga yang ada di poligon sebagai potongan-potongan kue terkecil yang dimulai di titik tersebut. Dengan ini, untuk $i$ bilangan bulat antara $0$ and $N-1$, kita sudah mendapatkan luas potongan kue yang direpresentasikan $\{i,\ (i+2) \text{ mod } N \}$.

Perhatikan jika kita sudah mendapatkan luas potongan kue yang direpresentasikan $\{x, y\}$, kita dapat mendapatkan luas potongan kue yang direpresentasikan $\{x, (y+1)\text{ mod } N \}$ dengan menambahkan luas potongan $\{x, y\}$ dan luas segitiga yang dibentuk titik $x$, $y$, dan $(y+1)\text{ mod } N$. Dengan ini, kita bisa dengan mudah mencari luas potongan kue yang kita perlukan.

Gunakan logika yang mirip dengan Dijkstra untuk memanfaatkan priority queue. Jika luas sebuah potongan kue lebih besar dari potongan kue terkecil ke-$U$ sementara, kita tidak perlu mencari potongan kue dari titik itu lagi.

Kompleksitas waktu: $O(max(N, U) \text{ log } N)$
Note: log $N$ merupakan kompleksitas waktu untuk priority queue.