---
# System prepended metadata

title: Pembahasan Soal Pindah Rumah

---

# Pembahasan Soal Pindah Rumah
Perhatikan bahwa urutan pengangkutan tidak berpengaruh. Hal yang penting hanyalah banyak barang yang diangkat oleh sebuah drone/truk.
## Subsoal 1
Untuk subsoal ini, kita cukup mencoba setiap kemungkinan pemindahan barang menggunakan truk/drone yang dimiliki.

Kompleksitas: $O(1)$

## Subsoal 2
Perhatikan jika $B = 0$, maka kita hanya perlu memperhatikan berat dari barang yang diangkat. 

Kita dapat menggunakan algoritma greedy dengan mengurutkan drone dan barang yang akan diangkat berdasarkan berat. Mulai dari barang yang paling berat, kita akan angkat barang tersebut dengan drone yang mampu mengangkat barang tersebut yang masih paling sedikit mengangkut barang.

Perhatikan bahwa jika kita bisa memindahkan semua barang dalam $T$ waktu, maka kita pasti bisa memindahkan semua barang dalam $T + 1$ waktu. Ini merupakan sifat monotonik dimana kita bisa menggunakan *binary search the answer* (bsta).

Kompleksitas: $O(A\text{log}A + T\text{log}T)$

## Subsoal 3
Untuk mencari apakah dengan waktu $T$ memungkinkan untuk memindahkan semua barang, kita bisa mencoba untuk memindahkan barang secara brute force.

Pada awalnya kita harus mengurutkan berat truk dan drone secara menurun karena berat yang besar lebih optimal dipasangkan dengan berat yang besar juga.

Oleh karena itu, kita bisa melakukan DP yang memiliki 4 state. $dp[\text{idx_truk}][\text{idx_drone}][\text{berat}][\text{ukuran}] = \text{bisa dicapai/tidak}$. Artinya, jika sudah memikirkan semua barang yang memiliki berat dan ukuran yang lebih besar dari yang ada di state DP, apakah mungkin untuk dilakukan menggunakan $\text{idx_truk}$ dan $\text{idx_drone}$ pertama. Pemeriksaan DP ini akan berjalan dalam $O(N^4)$ dengan syarat berat dan ukuran dikecilkan menggunakan *coordinate compression*.

DP ini memiliki banyak edge case dalam transisinya, tidak disarankan untuk mengerjakan subsoal ini.

Kompleksitas: $O(N^4)$

## Subsoal 4
Kita bisa menggabungkan ide *binary search the answer* dengan ide *greedy* yang sudah di dapat. Akan tetapi, kita harus membuat ide *greedy* kita bekerja untuk berat dan ukuran. 

Misalnya, awalnya kita pilih untuk mengatur pengiriman dari truk terlebih dahulu. Perhatikan bahwa barang-barang yang paling optimal dibawa oleh truk adalah membawa barang berat sebanyak mungkin agar nanti pada waktu mengatur pengiriman dari drone lebih mudah.

Oleh karena itu, kita pertama melakukan sorting untuk elemen-elemen dari ukuran kecil ke besar. Setelah itu, untuk setiap truk kita akan berusaha untuk mengangkat barang dengan berat yang paling tinggi yang ukurannya kurang dari maksimal ukuran truk. 

Trik untuk melakukan implementasi dengan priority queue adalah ketika sedang memproses 

Untuk drone, masalahnya bisa diselesaikan seperti pada subsoal 2.

Subsoal juga bisa berfungsi memberi poin kepada orang yang sudah mendapat ide full solution tetapi menggunakan set atau implementasinya lambat.

Kompleksitas: $O((A+B)^2\text{log}T)$

## Subsoal 5
Kita bisa mempercepat proses pencarian barang dengan berat tertinggi yang memiliki tinggi kurang dari maksimal ukuran truk.

Menyimpan barang dengan berat yang paling tinggi bisa dilakukan dengan priority queue. Masukkan semua barang yang tingginya kurang dari ketinggian sekarang ke dalam priority queue tetapi urutkan priority queue berdasarkan berat.

Kompleksitas: $O((A + B)\text{log}(A+B)\text{log}T)$