# Pembahasan Latihan 2
## A. Bola Basket Bersama
### Pembahasan oleh Joel Gunawan
### Subsoal 3
Perhatikan bahwa kemampuan pelatihan Pak Chanek tidak berpengaruh. Kita cukup mencari berapa banyak orang paling sedikit yang kita butuhkan untuk mengalahkan lawan. Setelah itu, kita bisa hitung berapa maksimal kemenangan yang mungkin.

### Subsoal 4
Cara paling optimal untuk meminimalkan orang yang dibutuhkan adalah dengan cara mengelompokkan orang lain dengan orang yang memiliki kekuatan paling besar. Jika ada beberapa pilihan orang yang bisa dikelompokkan kita akan mengelompokkan orang yang memiliki kekuatan terkecil. Untuk mencari orang dengan kekuatan terbesar dan kekuatan terkecil, kita bisa cari secara manual sehingga kompleksitas akhirnya adalah $O(N^2)$.

### Subsoal 5
Untuk mempercepat pencarian orang dengan kekuatan terkecil/terbesar, kita bisa mengurutkan kekuatan pemain terlebih dahulu, lalu orang terkecil akan ada di indeks paling kecil dan orang terkuat akan ada di indeks paling besar. Kita bisa menggunakan two pointers ataupun [deque](https://cplusplus.com/reference/deque/deque/).

## B. Djio dan Kombo
### Pembahasan Soal Asli oleh Albert Yulius Ramahalim (ditulis ulang oleh Joel Gunawan)
Pembahasan soal asli bisa dilihat di [sini](https://tlx.toki.id/problems/bnpchs-2023-penyisihan/E).

Berikut merupakan solusi *binary search*

Perhatikan bahwa dalam menjalankan algoritma pada soal, suatu karakter $S_i$ hanya akan masuk paling banyak dua kali ke $p$. Maka, rintangan utamanya adalah memeriksa dengan cepat apakah $p$ merupakan prefiks dari suatu kombo $C_j$.

Apabila semua kombo telah diurutkan secara leksikografis (berdasarkan alfabet), maka didapatkan bahwa
- jika $p$ merupakan prefiks dari suatu kombo, kombo-kombo dengan $p$ sebagai prefiksnya merupakan subarray dari array kombo yang telah diurutkan, dan
- jika $p$ kosong, maka $p$ dianggap merupakan prefiks dari seluruh kombo dalam array.

Oleh karena itu, kita dapat menyimpan dua nilai $l$ dan $r$ yang berturut-turut merupakan batas kiri dan batas kanan subarray kombo-kombo yang memiliki $p$ sebagai prefiksnya. Saat memperpanjang $p$ dari panjang $x - 1$ menjadi $x$, kita dapat menggunakan binary search dalam rentang $[l,r]$ untuk mencari rentang baru yang karakter ke-$x$-nya sama dengan karakter ke-$x$ dari $p$ yang baru saja kita masukkan. Apabila rentang tersebut ada, maka masih terdapat suatu kombo $C_j$ sehingga $p$ merupakan prefiks dari kombo tersebut.

Selain itu, apabila terdapat suatu kombo $C_j$ sehingga $p=C_j$, maka $C_j$ pasti terletak pada ujung kiri dari rentang $[l,r]$ sekarang, karena secara leksikografis lebih kecil dari kombo-kombo lainnya dalam rentang tersebut. Untuk memastikan solusi ini tetap berjalan cukup cepat, kita cukup membandingkan panjang $p$ dengan kombo pada indeks $l$.

Kompleksitas waktu:
$O(L\text{ log }L+NlogM)$, dengan $L=\sum_{i=1}^{M}|C_i|$ merupakan jumlah dari panjang semua kombo.

## C. File Explorer
### Pembahasan oleh Radhya Cahya Kusuma
Perhatikan bahwa struktur sistem direktori tersebut membentuk sebuah tree dengan root di ```local```. Supaya lebih jelas, bisa melihat contoh yang diberikan soal

local/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

Di sini, ```file2``` merupakan child dari ```folder2```, ```folder2``` merupakan child dari ```folder1```, dan ```folder1``` merupakan child dari ```local```.

Berikut visualisasi tree-nya

Apabila kita berada di suatu direktori:
- Tiap mengakses **direktori** di bawahnya, kita harus menuliskan ```[nama direktori]/```. Artinya, butuh karakter sebesar panjang nama direktori + 1 (untuk slash).
- Tiap mengakses **direktori** di atasnya, kita harus menuliskan ```../```. Artinya, butuh 3 karakter.
- Tiap mengakses **file** di bawahnya, kita harus menuliskan ```[nama file]```. Artinya, butuh karakter sebesar panjang nama file.

Untuk mempermudah, anggap saja panjang karakter yang di relative path untuk mengakses direktori lain sebagai jarak antar node.

Kita ingin mencari suatu direktori dengan total jarak ke semua file paling minimal.

### Subsoal 1
Untuk setiap **direktori**, coba lakukan graph traversal (BFS ataupun DFS). Hitung jumlah total jarak dari direktori tersebut ke setiap file. Cari yang paling minimal.

Kompleksitas: $O(N^2)$

### Subsoal 2 (AC)
Di cara sebelumnya, kita harus menghitung jarak ke setiap file untuk setiap direktori, sehingga kompleksitasnya $O(N^2)$. Bisakan kita menghitung jarak total hanya untuk satu direktori saja, lalu perhitungannya kita pakai lagi untuk direktori lainnya? Yaps, DP on Tree.

Coba bayangkan kita sudah menghitung jarak total untuk direktori bernama `parent`, anggap nilainya $V_p$. Saat ini, kita harus menghitung total jarak untuk direktori `child` yang berada tepat di bawahnya.

Awalnya, set jarak total ke semua file untuk direktori `child`, $V_c$ = $V_p$

Perhatikan bahwa hanya terdapat 2 kasus untuk semua file:
1. File tersebut merupakan descendant dari direktori `child` (di bawahnya).
Awalnya, dari `parent` kita harus ke direktori `child` baru dapat menuju file ini. Karena saat ini kita sudah berada di d `child`, maka ini tidak perlu. $V_c$ akan berkurang sebesar panjang nama direktori `child` + 1.
2. File tersebut bukan merupakan descendant dari direktori `child`.
Sekarang, kita harus mengakses direktori `parent` dengan "../" sebelum dapat mengakses file tersebut. $V_c$ akan bertambah sebesar 3.

Hitung jarak total dari direktori `local` ke seluruh file dengan cara subsoal 1. Dalam traversal tersebut, maintain juga banyak file yang merupakan descendant dari setiap direktori dalam array $D$. Lakukan DFS sekali lagi untuk menghitung jarak total dari direktori di bawahnya. Untuk menghitung jarak semua file ke direktori sekarang, gunakan rumus $V_c = V_p - (L_c + 1) * D_c + 3 * (N - D_c)$ dengan $L_c$ adalah panjang nama direktori sekarang. Cari jarak semua file ke direktori yang paling minimal. AC.

Kompleksitas: $O(N)$

## D. Permainan ABC
### Pembahasan Soal Asli oleh Sayed (Ditulis ulang oleh Joel Gunawan)
Pembahasan soal asli bisa dilihat di [sini](https://tlx.toki.id/problems/osa-2024-final/A).

### Subsoal 4
Kita dapat melakukan Brute Force pada seluruh nilai bilangan bulat positif $B$ yang kurang dari $A$ lalu melakukan simulasi pada permainan hingga $B$ tidak lagi positif. Banyaknya langkah permainan kira-kira adalah $\text{log}A$ kali langkah.

Kompleksitas pada suboal ini adalah $O(A\text{log}A)$.

### Subsoal 5
Perhatikan bahwa untuk sembarang nilai $B$, baik nilai $A$ dan nilai $B$ untuk setiap iterasi akan habis dibagi dengan $\text{gcd}(A,B)$. Karena $A$ habis dibagi $9$, kita bisa coba mengatur $B=k \times A/9$ untuk suatu bilangan bulat positif $1 \le k \le 8$. Langkah ini sama saja seperti langkah saat mengecek $A=9$.

Kompleksitas pada subsoal ini adalah $O(1)$.

### Subsoal 6
Mari kita lakukan proses permainan secara terbalik dari akhir langkah hingga awal langkah. Urutan proses permainan terbalik ini secara berturut-turut adalah sebagai berikut:

- Ubah nilai $C$ menjadi $B$.
- Ubah nilai $B$ menjadi $A$.
- Ubah nilai $A$ menjadi $C+B$.

*Without Loss of Generality*, asumsikanlah nilai $A$ dan $B$ pada akhir permainan secara berturut-turut adalah $k$ dan $0$ sehingga Sayed menang. Jika kita simulasikan proses permainan secara terbalik ini maka kita akan dapatkan pola berikut:

- Pada akhir permainan, nilai $B$ adalah $0$ dan nilai $A$ adalah $k$.
- Setelah itu nilai $C$ adalah $0$, nilai $B$ adalah $k$, dan nilai $A$ adalah $C+B=k$.
- Setelah itu nilai $C$ adalah $k$, nilai $B$ adalah $k$, dan nilai $A$ adalah $C+B=2k$.
- Setelah itu nilai $C$ adalah $k$, nilai $B$ adalah $2k$, dan nilai $A$ adalah $C+B=3k$.
- Setelah itu nilai $C$ adalah $2k$, nilai $B$ adalah $3k$, dan nilai $A$ adalah $C+B=5k$.

Jika kita melakukan proses ini berkali-kali kita akan dapatkan bahwa nilai $A$ akan berbentuk kelipatan $k$ dari suatu suku pada deret fibonacci. Anggaplah nilai $A$ yang Parvez pilih berbentuk $kF_n$ di mana $F_n$ adalah suatu suku ke-$n$ pada deret fibonacci dan $k$ adalah suatu bilangan bulat positif. Maka nilai $B$ yang harus Sayed pilih adalah $kF_{n−1}$. Demikian Sayed dapat menang jika $A$ berbentuk $kF_n$ di mana $F_n \neq 1$, sebaliknya Sayed tidak dapat menang.

Demikian kita hanya perlu men-generate seluruh suku fibonacci kurang dari atau sama dengan $A$ hingga ditemukan suku $F_n$ yang membagi habis $A$. Jawabannya adalah $\frac{A \times F_{n - 1}}{F_n}$ atau $−1$ jika tidak ada $F_n$ yang memenuhi.

Kompleksitas pada subsoal ini adalah $O(\text{log}A)$.

## E. 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.

## F. Eksplorasi Planet
### Pembahasan oleh Matthew Hutama Pramana
Perhatikan bahwa banyak robot yang dibutuhkan untuk melakukan eksplorasi suatu pulau $i$ adalah sebanyak $C(Pi + Li, Pi)$. Untuk menghitung nilai kombinasi ini dapat dengan melakukan precompute factorial, dan mendapatkan nilai invers modulo dengan metode binary exponentiation.

Untuk menghitung nilai dari setiap kepulauan dapat dengan melakukan DFS, dimulai dari nomor pulau terkecil yang belum dijelajahi, hingga semua pulau sudah terjelajahi.

Kompleksitas waktu: $O(N \text{ log mod})$, $N$ untuk melakukan DFS dan $\text{log Mod}$ untuk menghitung nilai kombinasi yang merepresentasikan jumlah robot yang dibutuhkan dalam suatu pulau.
## G. Pertahanan Diagonal
### Pembahasan oleh Audra Aurora Izzani

Perhatikan bahwa petak terlarang yang terletak di $(x, y)$ hanya bisa diserang benteng yang terletak di $(x, x)$ atau $(y, y)$. Namun, karena sebuah petak terlarang hanya boleh diserang satu benteng, maka kita harus menyingkirkan satu di antara $(x, x)$ dan $(y, y)$.

Hubungan antara benteng-benteng dapat direpresentasikan dalam graf. Buat $N$ node untuk merepresentasikan tiap benteng dan $M$ edge untuk merepresentasikan setiap pasangan benteng yang tidak boleh ada di papan bersama.

Perhatikan jika graf tersebut dibagi menjadi dua sebagaimana sehingga satu subgraf terdiri dari benteng yang tidak disingkirkan dan subgraf yang lain terdiri dari benteng yang disingkirkan, tidak boleh ada edge yang menghubungkan sebuah node di satu subgraf ke subgraf yang sama. Dengan ini, tujuan kita berubah menjadi mengecek apakah graf ini bipartit.

Penjelasan lebih lengkap dapat dilihat di [sini](https://en.wikipedia.org/wiki/Bipartite_graph). Intinya, sebuah graf disebut bipartit jika semua node bisa diwarnai dengan dua warna sebagaimana sehingga tidak ada edge yang menghubungkan dua node dengan warna yang sama. Pengecekan apakah sebuah graf bipartit dapat dilakukan dengan DFS (atau BFS).

Kompleksitas waktu: $O(N)$

## H. Suhu
### Pembahasan oleh Kevin Cornellius Widjaja
### Subsoal 1
Karena nilai N dan M kecil, kita bisa menyimpan semua suhu pengunjung dalam sebuah array dan melakukan sorting.

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

### Subsoal 2
Kita bisa melihat bahwa untuk setiap baris yang sama, suhu pengunjung selalu berurutan secara naik. Sehingga, untuk mencari pengunjung dengan suhu terkecil yang ke $L_k$, kita dapat melakukan *Binary Search The Answer (BSTA)*.

Untuk suatu nilai (misalnya $M$), kita dapat menghitung banyaknya pengunjung dengan suhu $\leq M$.
Banyaknya pengunjung dengan suhu $\leq M$ sama dengan banyaknya pasangan nilai $i$ dan $j$ yang memenuhi sehingga:
$\dfrac{B+j}{A+i}\leq M$, atau secara formal $\sum_{i=i}^N \lfloor M*(A+i) - B \rfloor$

Setelah mencari nilai $M$ yang terdekat dengan $L_k$, kita bisa mengiterasi setiap nilai $i$, untuk mencari perbedaan nilai $j$ yang paling sedikit.

Kompleksitas Waktu: $O(QN\text{log}X)$, dengan $X$ sebagai nilai suhu terbesar yang mungkin.

## I. Kue Sus
### Pembahasan oleh Vincent Gaudeo Lie dan Joel Gunawan
### Subsoal 1
Untuk subsoal ini, kita bisa membuat $1$-*modder* maka seluruh isi $A$ bisa di-modulo menjadi $0$. Biaya yang dibutuhkan selalu $2$.

### Subsoal 2
Perhatikan bahwa $k$-*modder* maksimal yang bisa digunakan hanya sebanyak nilai maksimal dari $A_i$. Oleh karena itu, kita dapat mencoba setiap kemungkinan pembelian $k$-*modder*, yaitu sebanyak $2^{A_{maks}}$. Dari situ, kita dapat mencoba secara apakah dengan $k$-*modder* yang ada apakah dapat merubah dari array $A$ menuju $B$. Kita dapat memisalkan perubahan angka dari array $A$ dengan $k$-*modder* sebagai graf dan mencari apakah dari suatu node kita bisa mencapai node lain. Anggap bilangan-bilangan yang ada $(1...200)$ sebagai node. Koneksinya adalah dengan operasi modder. Contohnya apabila dari bilangan $14$ dan kita punya $2, 3,$ dan $5$ modder, maka $14$ punya koneksi ke $14 % 2 = 0, 14 % 3 = 2,$ dan $14 % 5 = 4$.

### Subsoal 3 & 4
Tidak terpikirkan

### Solusi Penuh
Observasi utama adalah bahwa $2^{k} > 2^{k-1} + 2^{k-2} + ... + 2^{0}$
Ingat pula bahwa 0-modder tidak ada, $k$ minimum adalah $1$.
Sehingga, akan lebih menguntungkan bagi kita untuk memilih semua angka dari $1$ sampai $k-1$ dibandingkan memilih $k$. Hal ini memperbolehkan kita menggunakan konsep greedy.
Kita akan mencoba untuk semua bilangan $x$ mulai dari $1$, apakah kita bisa mengubah $A$ menjadi $B$ hanya menggunakan angka-angka dari $1$ sampai $x$. Hal ini bisa dilakukan sama persis dengan metode untuk subsoal 2.

Setelah menentukan $k$ maksimum, kita akan menghilangkan angka-angka yang kita tidak perlukan.
Untuk proses penghilangan ini, kita mulai dari $k-1$ sampai $1$. Kita akan coba dengan apabila suatu angka dihilangkan, apakah semua bilangan di $A$ masih bisa diubah menjadi $B$?
Dengan demikian, dapatlah kita total biaya yang diperlukan.
Kompleksitas waktu: $O(N^{2} * max(A_i))$
Kompleksitas ini didapat dari:
1. Mencari $k$ terbesar: $max(A_i) * dfs$
2. Mencari bilangan yang tidak perlu: $k * max(A_i) * dfs$

Kompleksitas dfs adalah $O(N)$
Kode bisa dilihat di https://gist.github.com/vincentlie06/83197be6690cc12de78c4dd4c96d387e

## J. Bidak Merah dan Biru
### Pembahasan Soal Asli oleh Abdul Malik Nurrokhman (ditulis ulang oleh Joel Gunawan)
Menggunakan DP dengan 3 state, yaitu: langkah yang sudah Anda lakukan, baris tempat bidak merah, dan baris tempat bidak biru. Transisinya adalah gerakan setiap bidak masing-masing ke kanan atau ke bawah. Jika kedua bidak berada di posisi yang sama, maka salah satunya di-xor dengan $K$. Jika dihitung, maka kompleksitasnya $O(N^2M)$. Namun, perlu diperhatikan bahwa nilai $\text{min}(N,M) \le \sqrt{NM}$ sehingga kompleksitasnya menjadi $O(NM\sqrt{NM})$. Jika $N>M$ maka matrix tersebut harus di-transpose.

Kompleksitas: $O(NM\sqrt{NM})$