---
# System prepended metadata

title: Pembahasan Soal Belajar Bersama

---

# Pembahasan Soal Belajar Bersama
## Subsoal 1
Cobalah setiap urutan penghapusan yang mungkin menggunakan DP Bitmask. Untuk setiap penghapusan, periksalah apakah mungkin untuk menghapus bit tersebut dengan angka yang diberikan.

Kompleksitas: $O(N^22^N)$

## Subsoal 2
Perhatikan bahwa urutan penghapusan yang optimal selalu menghapus dari angka yang paling besar. Hal ini benar karena angka paling besar jika dihapus akan membuat lebih mudah menghapus angka lain yang lebih kecil.

Selain itu, perhatikan bahwa jika $B$ bukan merupakan subsequence dari $A$, maka tidak ada jawaban.

Dari situ, kita dapat mencoba untuk menggunakan exploit kita secara strategis. Exploit yang paling susah untuk digunakan adalah exploit dengan range terbesar. Kita akan coba dengan urut memproses seluruh penghapusan dari yang terbesar hingga yang terkecil. Kita akan mencari segmen terpanjang dimana angka sekarang merupakan maksimal, lalu mencari eksploit terbesar yang tidak lebih besar dari ukuran segmen sekarang.

Kita memperlukan $O(N)$ operasi untuk memeriksa segmen terpanjang di setiap penghapusan. Karena penghapusan bisa ada sebanyak $O(N)$, maka kompleksitasnya tinggal dikali saja.

Kompleksitas: $O(N^2)$

## Subsoal 3 dan 4
Jika $A$ urut, maka $B$ juga harus urut. Oleh karena itu, sebenarnya subsoal 3 dan 4 merupakan batasan yang sama.

Untuk subsoal ini, kita dapat mencari segmen terpanjang dengan mudah. Panjang segmen yang bisa dihapus selalu adalah angka itu sendiri. Oleh karena itu, kita bisa membuat operasi pemeriksaan segmen terpanjang menjadi $O(1)$.

Kompleksitas: $O(N)$

## Subsoal 5
Kita dapat memeriksa segmen terpanjang tiap penghapusan dengan menjalankan nearest smaller element yang dimodifikasi. Kita akan mencari nilai lebih besar terdekat yang bukan merupakan elemen yang dihapus. Setelah itu, untuk mencari banyak elemen yang terhapus di dalam segmen yang kita pilih, bisa gunakan segment tree dan memproses urut dari terbesar ke terkecil. Oleh karena itu, kompleksitas setiap penghapusan menjadi $O(\text{log}N)$

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