# Pembahasan Latihan 3

## A. Cari Nilai Root
### Pembahasan oleh Vincent Valentino Oei
Perhatikan bahwa nilai root merupakan jumlah nilai setiap node lainnya, karena setiap node selain root pasti merupakan anggota dari subtree root.

Dengan demikian, jumlah dari $V_i$ untuk setiap $1\leq i\leq N$ sama dengan nilai root ditambah jumlah nilai setiap node lainnya, yakni dua kali nilai root.

Sehingga jawabannya adalah $\frac{1}{2} * \displaystyle\sum_{i=1}^N{V_i}$

Kompleksitas waktu: $O(N)$

## B. Aduh, Soal Mengurutkan
### Pembahasan oleh Joel Gunawan
Perhatikan bahwa di soal ini kita diminta untuk melakukan pengurutan dengan perbandingan yang khusus. Oleh karena itu, kita dapat menggunakan fungsi *sort* yang ada di STL yang digunakan dengan *custom compare function*. Dengan kata lain, kita membuat fungsi perbandingan sendiri sesuai yang diminta oleh soal. Berikut adalah referensi untuk [*custom compare function*](https://www.geeksforgeeks.org/comparator-in-cpp/)

## C. Empat Kuadrat
### Pembahasan Asli oleh Prabowo Djonatan (diterjemahkan oleh Joel Gunawan)
Tautan pembahasan asli dapat dilihat [disini](https://tlx.toki.id/problems/ksn-2020/0B)

### Kasus Uji 1
Dapat dengan mudah dilihat bahwa $1 = 1 + 0 + 0 + 0 = 1^2 + 0^2 + 0^2 + 0^2$. Anda dapat mengeluarkan ```1 0 0 0```.

### Kasus Uji 2
Dapat dengan mudah dilihat bahwa $10^{18} = 10^{18} + 0 + 0 + 0 = {10^9}^2 + 0^2 + 0^2 + 0^2$. Anda dapat mengeluarkan ```1000000000 0 0 0```.

### Kasus Uji 4
Dapat dengan mudah dilihat bahwa $10^8 + 1 = 10^8 + 1 + 0 + 0 = {10^4}^2 + 1^2 + 0^2 + 0^2$. Anda dapat mengeluarkan ```10000 1 0 0```.

### Kasus Uji 5
Dapat dengan mudah dilihat bahwa $10^9 = 9 \times 10^8 + 10^8 + 0 + 0 = (3 \times 10^4)^2 + {10^4}^2 + 0^2 + 0^2$. Anda dapat mengeluarkan ```30000 10000 0 0```.

### Kasus Uji 3
Untuk kasus uji ini tidak semudah yang sebelumnya tetapi dapat dilihat bahwa $2020 = 40^2 + 20^2 + 4^2 + 2^2$. Anda dapat mengeluarkan ```40 20 4 2```.

### Solusi Penuh
5 kasus uji di atas akan mendapatkan $50$ poin. Kita harus menggunakan komputer untuk poin yang lebih banyak.

Kita dapat mencoba sebuah solusi yang menggunakan *greedy*.
- Ambil nilai terbesar $a$ sehingga $a^2 <= N$.
- Kurangi $N$ dengan $a^2$.
- Ulangi untuk $b, c, d$.

Algoritma ini akan mendapatkan poin sebagai berikut:
- $10$ poin untuk kasus uji 1, 2, 4, 5, 8.
- $9$ poin untuk kasus uji 3.
- $7$ poin untuk kasus uji 6.
- $5$ poin untuk kasus uji 7.
- $4$ poin untuk kasus uji 10.
- $0$ poin untuk kasus uji 9.

Totalnya adalah $75$ poin.

Solusi penuh membutuhkan sedikit modifikasi dari teknik sebelumnya. Kita akan mencoba $100$ angka terbesar yang mungkin untuk masing-masing dari $a, b, c, d$. Program ini akan berjalan dengan waktu keseluruhan kurang dari 1 detik untuk semua kasus uji yang diberikan.

### Catatan
Berdasarkan teorama [berikut](https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem) ada setidaknya satu solusi untuk sebuah nilai $N$.

## D. Tzaph dan FPB KPK
### Pembahasan oleh Maximilliano Utomo Quok (ditulis ulang oleh Joel Gunawan)
Misalkan ada dua bilangan bulat positif $A$ dan $B$, dengan $A=kx$, $B=ky$, dan $FPB(x,y)=1$. Maka $FPB(A,B)=k$ dan $KPK(A,B)=kxy$.

Perhatikan bahwa $A×B=FPB(A,B)×KPK(A,B)$.
Oleh karena itu, soal ini dapat direduksi menjadi “Carilah $A$ dan $B$ sehingga $FPB(A,B)=1$ dan $KPK(A,B) = \frac{KPK_{input}}{FPB_{input}}$”, lalu $A$ dan $B$ akhir dikalikan dengan $FPB_{input}$.

Kita bisa selesaikan soal tereduksi dengan cara mencoba semua bilangan $X$ yang kurang dari atau sama dengan $KPK(A,B)$ sehingga memenuhi $FPB(X, \frac{KPK}{X}) = 1$. Ambilah hasil $X + \frac{KPK}{X}$ terkecil. Nilai $A$ dan $B$ merupakan $X$ dan $\frac{KPK}{X}$.

Perhatikan pula dalam definisi ini, KPK habis dibagi oleh FPB. Maka jika KPK yang diberikan tidak habis dibagi oleh FPB, maka tidak ada solusi.

Kompleksitas waktu: $O(\sqrt{N})$

## E. Angka Cantik
### Pembahasan oleh Galangkangin Gotera (ditulis ulang oleh Joel Gunawan)
Pertama-tama, dijamin pasti ada jawaban. Tidak ada kemungkinan input yang menyebabkan jawaban $-1$.

### Subsoal 1
Kita bisa cek semua kemungkinan angka. Total hanya $200 \, 000$ angka yang mungkin di cek.

### Subsoal 2
Buat angka $T$ yang merupakan konkatenasi dari semua digit favorit bukan $0$. Misal digit-digit tersebut $1, 4, 5, 6, 9, T = 14569$. Salah satu jawaban yang mungkin adalah $TTT0000$. Hal ini karena sifat dari angka yang habis dibagi 3 yaitu penjumlahan digit-digitnya harus habis dibagi 3.

Kompleksitas: $O(N)$

### Subsoal 3
Kita bisa membuat BFS bitmask sebagai berikut: misalkan $can[m][mask]$ adalah sebuah boolean yang menyatakan bisa/tidak membuat digit yang jika dimodulo $M$ bernilai $m$ dan telah menggunakan digit-digit pada mask. Pada mulanya $can[0][0] = 0$. Dari state $(m, mask)$ kita bisa transisi ke state $((m \times 10) D_i, mask | 2^i)$.

Kompleksitas: $O(2^NM)$

### Subsoal 4
Untuk kemudahan, anggap digit bukan nolnya $T$. Buat sekuens angka $S = (, T, TT, TTT, TTTT, ..., TTTTT....TTT)$ dimana $S_i$ adalah angka dengan $i$ buah digit $T$. Hitung semua $S_i$ modulo $M$, sebut $m_i$ sebagai $S_i \text{ mod } M$. Menghitung ini dengan cepat dapat dilakukan dengan modulo angka sebelumnya yaitu $m_{i + 1} = (m_i \times 10 + T) \text{ mod } M$. Anggap ada $i$ dan $j$ dimana $m_i = m_j$. Maka didapati $S_i - S_j = 0 \text{ mod } M$. Selain itu, angka ini juga masih menjaga sifat hanya terdiri dari digit-digit cantik Bu Chanek.

Kompleksitas: $O(M)$

### Subsoal 5
Untuk setiap digit, kita bisa mencari angka yang jika di modulo akan menghasilkan $0$ dengan menggunakan digit itu sendiri dan $0$ (algoritma subsoal 4). Anggap angka-angka tersebut $S_1, S_2, S_3, ..., S_n$. Jelas bahwa jika $S_i \text{ mod } M = 0, (S_i \times 10) \text{ mod } M = 0$. Salah satu angka yang valid adalah $S_1S_2S_3...S_n$, konkatenasi dari setiap angka-angka.

Kompleksitas: $O(NM)$

### Catatan
[Kode Sumber](https://ideone.com/XsOAnS)

## F. Pohon Paaf
### Pembahasan oleh Joel Gunawan

### Subsoal 2
Untuk subsoal ini, perhatikan bahwa di setiap sel $(1, x)$, sel tersebut termasuk ke dalam subgrid hanya jika terdapat *pohon paaf* yang tumbuh di sebuah sel $(1, y)$ dan $(1, z)$ dimana $x \le y$ dan $x \ge z$. Dengan kata lain, terdapat *pohon paaf* yang tumbuh di kiri dan kanan dari $x$ atau ada *pohon paaf* yang tumbuh di titik $x$.

Jika di kiri $x$ ada $a$ petak subur, di $x$ ada $b$ petak subur, di kanan $x$ ada $c$ petak subur, maka banyak cara pertumbuhan *pohon paaf* di mana petak $(1, x)$ termasuk ke dalam subgrid dapat dihitung dengan persamaan berikut:

$$(2^b-1) \times 2^{N - b} + (2^a - 1) \times (2^c - 1)$$

Kompleksitas: $O(N + C)$

### Subsoal 4
Perhatikan bahwa syarat untuk suatu sel $(x, y)$ merupakan bagian dari subgrid untuk suatu kemungkinan pertumbuhan *pohon paaf*, maka dari semua lokasi *pohon paaf* yang tumbuh, syarat berikut harus terpenuhi:

$$min_r \le x \le max_r, min_c \le y \le max_c$$

Kita dapat dengan lebih mudah menghitung berapa banyak pertumbuhan *pohon paaf* yang tidak memenuhi syarat tersebut. Misalnya ada $4$ himpunan, yaitu:

- $U = \text{Himpunan yang menyatakan banyak petak subur dengan nilai } r < x$
- $L = \text{Himpunan yang menyatakan banyak petak subur dengan nilai } c < y$
- $D = \text{Himpunan yang menyatakan banyak petak subur dengan nilai } r > x$
- $R = \text{Himpunan yang menyatakan banyak petak subur dengan nilai } c > y$

Secara intuitif, banyak cara yang tidak memenuhi adalah:

$$2^{N(U)} - 1 + 2^{N(L)} - 1 + 2^{N(D)} - 1 + 2^{N(R)} - 1$$

Nantinya, karena ada beberapa duplikat, maka akan dikurangi

$$(2^{N(U \cap L)} - 1) + (2^{N(U \cap R)} - 1) + (2^{N(D \cap L)} - 1) + (2^{N(D \cap R)} - 1)$$

Menggunakan inklusi-eksklusi dasar, kita dapat mengetahui berapa banyak cara yang memenuhi.

Untuk mencari nilai-nilai $U, L, D, R$ kita dapat menggunakan *prefix sum* 2D.

Kompleksitas: $O(RC)$

## G. Segitiga Bermuda
### Pembahasan oleh Kevin Cornellius Widjaja

### Subsoal 1 ($1 \leq N \leq 500$)

Untuk membuat sebuah segitiga bermuda yang valid, kita memerlukan 3 garis yang tidak sejajar. Dengan kata lain, kita memerlukan 3 garis yang memiliki **gradien** yang berbeda.

Sehingga, kita hanya perlu menyimpan gradien dari setiap garis dalam bentuk $a/b$. Dimana, $a = (A_i/FPB(A_i,B_i))$ dan $b = (B_i/FPB(A_i,B_i))$.

Untuk menghitung jawaban, kita cukup mengiterasi secara bruteforce 3 garis dengan gradien yang berbeda semua yang memenuhi.

Kompleksitas: $O(N^3)$

### Subsoal 2 ($1 \leq N \leq 5000$)

Perhatikan bahwa, kita bisa menyimpan setiap garis yang memiliki gradien yang sama, misalkan, definisikan banyak garis yang memiliki gradien $x = m_x$. Hal ini bisa dilakukan dengan menggunakan map.

Dengan begini, kita bisa secara naif mengiterasi 2 garis i dan j dimana mereka memiliki gradien yang berbeda, dan menghitung banyak garis ke-3 yang valid dengan $N-\sum(m_(gradien_i))-\sum(m_(gradien_j))$

Kompleksitas: $O(N^2 log N)$

### Subsoal 3 ($1 \leq N \leq 500000$)

Permasalahan ini bisa diselesaikan dengan prinsip **inklusi-eksklusi**
Perhatikan bahwa kita bisa menghitung semua kombinasi garis (baik yang valid maupun tidak valid dengan):
${N \choose 3} = \frac{N*(N-1)*(N-2)}{6}$

Untuk menghitung banyaknya garis yang **tidak** valid, untuk setiap gradien $x$,
- Banyaknya pasangan dimana gradien garis i,j dan k adalah $x$ = ${M_x \choose 3} = \frac{M_x*(M_x-1)*(M_x-2)}{6}$
- Banyaknya pasangan dimana gradien garis i dan j adalah $x$ = ${M_x \choose 2} * (N-\sum(M_x)) = \frac{M_x*(M_x-1)}{2} * (N-\sum(M_x))$

Sehingga, kita hanya perlu mengeksklusi nilai tersebut dari jawaban.
Kompleksitas: $O(NlogN)$

Note: Perlu diperhatikan beberapa nilai $B_i$ bisa berupa nilai 0
## H. Efek Anti Jerawat
### Pembahasan Asli oleh Pikatan Arya Bramajati (diterjemahkan oleh Joel Gunawan)
Tautan pembahasan asli dapat dilihat di [sini](https://tlx.toki.id/problems/compfest-15-jcpc-final/E)

Untuk sebuah nilai $w$, misal $f(w)$ adalah banyak cara memilih indeks hitam sehingga skor tepat $w$ dan $g(w)$ adalah banyakc ara memilih indeks hitam sehingga skor maksimal $w$. Dapat dilihat bahwa $f(w) = g(w) - g(w - 1)$.

Mari kita coba untuk menghitung $g(w)$. Pertama, kelompokkan elemen di $A$ ke dalam dua kelompok. Kelompok 1 mengandung elemen dengan nilai lebih dari $w$ dan kelompok 2 mengandung elemen dengan nilai tidak lebih dari $w$. Perhatikan bahwa satu-satunya syarat adalah kita tidak boleh membuat elemen manapun di kelompok 1 menjadi hitam atau hijau dan kita dapat melakukan apapun terhadap elemen di kelompok 2. Untuk memastikan tidak ada elemen di kelompok 1 yan ghitam atau putih, maka kita harus memastikan bahwa tidak ada indeks hitam yang kita pilih merupakan faktor dari salah satu indeks elemen di kelompok 1. Artinya, kita hanya perlu mencari suatu nilai $c$ yang melambangkan banyak indeks yang merupakan faktor dari setidaknya suatu indeks elemen yang terdapat di kelompok 1, maka nilai $g(w) = 2^{N - c} - 1$.

Jawaban untuk soal ini adalah jumlah dari $f(w) \times w$ untuk setiap nilai $w$ yang mungkin. Akan tetapi, kita hanya mempedulikan nilai $w$ dimana $f(w) \neq 0$ yang hanya terjadi jika $w$ sama dengan nilai dari suatu elemen di $A$.

Untuk menghitung $g(w)$ untuk setiap nilai $w$ yang diinginkan, kita dapat mengiterasi setiap elemen di $A$ dari nilai terbesar hingga terkecil. Tiap elemen yang kita iterasi, kita iterasi tiap indeks yang merupakan faktor dari indeks elemen yang kita iterasi dan menandai bahwa indeks tersebut merupakan bagian dari kelompok 1 sambil kita menghitung nilai sementara dari $c$.

Total iterasi yang dilakukan adalah banyak faktor dari tiap indeks, yaitu $N \text{log} N$.

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

## I. Djio dan Gerai Es Krim dan Teh
### Pembahasan Asli oleh Albert Yulius Ramahalim (ditulis ulang oleh Joel Gunawan)
Tautan pembahasan asli dapat dilihat di [sini](https://tlx.toki.id/contests/troc-34/problems/D)

Perhatikan bahwa Djio dapat bergerak antarlantai dan antarverteks secara independen satu sama lain. Oleh karena itu, kita dapat menentukan secara terpisah lantai dan verteks dari gerai yang dipilih.

#### Meminimumkan jumlah jarak antarlantai
Jumlah jarak antarlantai minimum yang dicari adalah $\text{min}_{1 \le L \le 10^9} \sum_{i = 1}^{K} |L - A_i|$.

Perhatikan bentuk fungsi $f(x) = |x - c|$ untuk suatu konstanta $c$. Dapat dilihat bahwa terdapat suatu nilai $L$ optimum sehingga terdapat $j (1 \le j \le K)$ yang memenuhi $L = A_j$.

Urutkan semua nilai $A_i$. JUmlah jarak antarlantai apabila $L = A_k$ kini dapat ditulis menjadi $\sum_{i = 1}^{k - 1} (A_k - A_i) + \sum_{i = k + 1}^K(A_i - A_k)$. Ini dapat dicari menggunakan *prefix sum* dalam $O(1)$ untuk suatu $k$.

Alternatifnya, perhatikan bahwa nilai $A_j$ yang optimum pasti merupakan emdian dari $A$.

Submasalah ini dapat diselesaikan dalam $O(N \text{ log }N)$.

#### Meminimumkan jumlah jarak antarverteks
Misalkan $\text{dist}(u, v)$ adalah jarak antara verteks $u$ dan $v$ pada *tree*. Jumlah jarak antarverteks minimum yang dicari adalah $\text{min}_{1 \le X \le N}\sum_{i = 1}^K \text{dist}(X, B_i)$.

Misalkan $F(u) = \sum_{i = 1}^K \text{dist}(u, B_i)$ untuk suatu verteks $u$ sebagai jumlah jarak semua verteks $B_i$ dari $u$. Kita akan menghitung $F(u)$ untuk semua $u$. Jawaban yang kita cari adalah $\text{min}_{1 \le X \le N} F(X)$.

Pilih verteks apapun, misalkan $r$ sebagai *root* dari *tree*. $F(r)$ dapat dicari dengan menggunakan DFS atau BFS. Sisa nilai $F$ untuk verteks-verteks lain akan kita cari menggunakan DFS atau BFS sekali lagi. Apabila kita mengetahui nilai $F(x)$, kita dapat mencari nilai $F(x)$ untuk $c$ child dari $x$. Saat "bergerak" dari $x$ ke $c$, kita "mendekat" sebanyak $1$ ke semua verteks $B_i$ yang berada di dalam subtree $c$ dan "menjauh" sebanyak $1$ dari semua verteks $B_i$ yang berada di luar *subtree* $c$. Banyaknya verteks $B_i$ di dalam suatu *subtree* dapat diprekomputasi di awal.

Terdapat juga solusi DP pada *tree* dengan *reroot* untuk submasalah ini.

Submasalah ini dapat diselesaikan dalam $O(N)$.

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

## J. Pertahanan Manado
### Pembahasan Asli oleh Ashar Fuadi (ditulis ulang oleh Vincent Valentino Oei)

Definisikan $DP_i$ sebagai harga minimum untuk membeli setidaknya satu botol (bisa lebih dari 1) dari masing-masing obat $j$ untuk setiap $j$ ($1\leq j \leq i$).

Tentunya $DP_0=0$ karena tidak ada obat yang perlu dibeli.

Kemudian untuk mendapatkan sebuah $DP_i$, kita perlu mengelompokkan paket-paket obat terlebih dahulu berdasarkan $B_i$ (seperti pada scheduling problem).

Definisikan $C_j$ sebagai kumpulan index paket dengan $B_i=j$.

Untuk setiap $j$ dari $1$ hingga $N$, kita dapat membeli sebotol obat $j$ dengan harga $S$ atau membeli paket dengan harga $P_i$ yang mencakup obat ke $j$.

Sehingga didapatkan transisi sebagai berikut:
$DP_i = min(DP_{i-1}+S, \\ \min_{c \in C_i}Q(A_{c}-1,B_{c}-1))$

Dengan $Q(x,y) = min(DP_x, DP_{x+1},...,DP_y)$

Namun solusi tersebut masih bekerja dalam $O(N^2)$ (tapi kalo implementasinya efisien, bisa AC).

Untuk solusi penuh, kita dapat menggunakan suatu data structure, seperti segment tree untuk mempercepat $Q(x,y)$ dari $O(N)$ menjadi $O(log\ N)$.

Alhasil solusi ini berjalan dalam $O(N\ log\ N)$.
AC!