# Proposal Ide Soal
## Pradita Dirgantara Competition

### Memindahkan kardus

**Deskripsi**

Diberikan sebuah grid berukuran $R \times C$. Setiap petak pada grid bisa merupakan salah satu dari beberapa tipe berikut :

- `S` : titik start
- `F` : titik finish
- `.` : petak kosong
- `#` : dinding

Pada titik start terdapat sebuah gudang. Di dalam gudang tersebut terdapat $N$ buah kardus berbentuk persegi panjang. Kardus ke $i$ berukuran $h_i \times w_i$

Kamu ingin memindahkan kardus-kardus dari titik start dengan ketentuan sebagai berikut :

- Pilih sebuah kardus yang masih ada di gudang dan keluarkan dari gudang. Anggap gudang berada pada koordinat $(r, c)$, maka ketika kardus $i$ dikeluarkan dari gudang, semua petak dari baris $[r, r+h_i-1]$ dan kolom $[c, c+w_i-1]$ harus kosong (tidak boleh ada petak `#`)
- Ulangi proses berikut : Geser kardus ke kiri/kanan/atas/bawah apabila pergeseran tersebut tidak terhalang oleh dinding (petak `#`).
- Apabila sudah ada bagian dari kardus tersebut yang mencapai titik finish, maka pergerakannya selesai

**Catatan : Kardus tidak bisa dirotasi**

Berikut ilustrasi pemindahan kardus berukuran $2 \times 3$ :


Kardus berukuran $3 \times 2$ tidak bisa dikeluarkan dari gudang karena terhalang dinding

Kardus berukuran $1 \times 4$ bisa dikeluarkan dari gudang. Namun tidak ada pergerakan yang memungkinkan bagi kardus tersebut untuk bisa sampai ke titik finish (`F`) karena terhalang dinding di tengah perjalanan

**Objective**
Tentukan banyak kardus maksimal yang bisa sampai di titik Finish

**Batasan**
- $1 ≤ N ≤ 5 \times 10^4$
- $1 ≤ h_i, w_i ≤ 5 \times 10^4$
- $1 ≤ R \times C ≤ 5 \times 10^4$

**Solusi**

Apabila suatu kardus berukuran $h \times w_1$ bisa mencapai finish, maka kardus berukuran $h \times w_2$ bisa mencapai finish juga apabila $w_2 ≤ w_1$

Maka dari itu, untuk suatu tinggi kardus $h$, kita bisa mencatat ada berapa banyak kardus lebar $w$ secara terurut menaik ($w_1 ≤ w_2 ≤ \ldots ≤ w_k$) kemudian kita bisa melakukan **binary search** untuk mencari nilai $w$ terbesar pada ukuran $h$ ini

Kasus terburuk terjadi ketika terdapat $\sqrt{N}$ buah kardus yang memiliki $h$ berbeda dan setiap ukuran $h$ memiliki $\sqrt{N}$ buah kardus berukuran $w$ berbeda-beda

kira kira seperti ini :

$h_1$ terdapat lebar $w_{1,1} ≤ w_{1,2} ≤ \ldots ≤ w_{1,\sqrt{N}}$
$h_2$ terdapat lebar $w_{2,1} ≤ w_{2,2} ≤ \ldots ≤ w_{2,\sqrt{N}}$
$\vdots$
$h_{\sqrt{N}}$ terdapat lebar $w_{\sqrt{N},1} ≤ w_{\sqrt{N},2} ≤ \ldots ≤ w_{\sqrt{N},\sqrt{N}}$

Untuk memeriksa apakah suatu kardus berukuran $h \times w$ bisa mencapai tiitk finish, kita bisa menggunakan BFS dengan kompleksitas $O(R \times C)$ dimana di setiap transisinya untuk memeriksa apakah gerakannya valid, kita bisa menggunakan 2D prefix sum untuk memeriksa apakah ada petak berisi dinding

Kompleksitas waktu untuk algoritma ini adalah :

$O(\sqrt{N} \times \text{log}_2\sqrt{N} \times R \times C)$

dalam kasus terburuk estimasi prosesnya adalah
$\sqrt{5 \times 10^4} \times \text{log}_2\sqrt{5 \times 10^4} \times 5 \times 10^4$
$= 223 \times 8 \times 5 \times 10^4$
$= 89,200,000$

**Tags**

- Binary Search
- Brute Force
- Optimization / Pruning
- BFS
- 2D Prefix Sum