# Pembahasan Latihan 4
## A. Golden Tickets
### Pembahasan oleh Muhammad Ayaz Dzulfikar
#### Diterjemahkan oleh Kevin Cornellius Widjaja

Kita akan mempertahankan sebuah struktur data yang berisi semua institusi yang diundang. Inisialisasi dengan tim-tim teratas sebanyak $M$ tim. Kemudian, iterasi tim-tim yang tersisa berdasarkan peringkat mereka. Untuk setiap tim, jika struktur data tidak mengandung institusi mereka dan kita belum menambahkan $K$ institusi baru, kita tambahkan institusi tersebut ke dalam struktur data dan nama tim ke dalam jawaban. Bergantung pada struktur data yang digunakan, kompleksitas waktu bisa menjadi $O(N^2)$ atau $O(N log N)$. Keduanya cukup untuk menyelesaikan masalah ini.

## B. Diet Plan
### Pembahasan oleh Muhammad Ayaz Dzulfikar
#### Diterjemahkan oleh Kevin Cornellius Widjaja
Mari kita tetapkan sebuah hari $i$. Perhatikan bahwa strategi optimal yang meminimalkan jumlah susu yang kita minum adalah dengan mengganti susu terbesar sebanyak $min(i,K)$ dengan biskuit. Oleh karena itu, memeriksa apakah memungkinkan untuk mempertahankan diet hingga hari ke-$i$ dapat dilakukan dalam $O(N log N)$: Urutkan susu dari hari $1$ hingga $i$, hapus susu terbesar sebanyak $min(i,K)$, dan periksa apakah jumlah susu yang tersisa tidak lebih besar dari $M$. Karena kita perlu memeriksa selama $n+1$ hari (dari $0$ hingga $n$), kompleksitas waktunya akan menjadi $O(N^2 log N)$.

Perlu dicatat bahwa solusi di atas dapat dioptimalkan menjadi $O(N log N)$, misalnya dengan menggunakan *priority queue*. Namun, ini tidak diperlukan untuk menyelesaikan masalah ini.

## C. Mendapatkan Kebahagiaan
### Pembahasan oleh Vincent Valentino Oei
String biner yang akan membuat Jojo bahagia adalah string biner yang hanya tersusun oleh segmen-segmen angka $1$ beruntun dan angka $0$ beruntun. Dengan panjang segmen seperti berikut:

- Setiap segmen angka $1$ harus memuat setidaknya $b_1$ angka $1$.
- Setiap segmen angka $0$ harus memuat setidaknya $b_0$ angka $0$.

Dengan demikian, maka kita dapat memecahkan masalah ini menjadi dua bagian.

Bagian pertama adalah menghitung banyaknya kombinasi segmen $1$ yang mungkin sehingga setiap segmen memiliki setidaknya $b_1$ angka $1$, lakukan hal ini juga untuk segmen $0$. Untuk menghitung banyaknya kombinasi segmen-segmen tersebut, anda dapat menggunakan stars and bars.

Bagian kedua adalah penggabungan jawaban dari bagian pertama. Misalkan setiap $0$ merepresentasikan suatu segmen dari angka $0$ dan setiap $1$ merepresentasikan suatu segmen dari angka $1$, maka terdapat 4 cara penyusunan yang berbeda, dibawah ini dicontohkan dengan sampel kecil:

- $01$, $0$ dahulu kemudian $1$. Jumlah segmen $1$ sama dengan jumlah segmen $0$.
- $10$, $1$ dahulu kemudian $0$. Jumlah segmen $1$ sama dengan jumlah segmen $0$ namun dengan urutan terbalik.
- $010$, $1$ dikelilingi $0$. Jumlah segmen $0$ sama dengan jumlah segmen $1$ ditambah satu.
- $101$, $0$ dikelilingi $1$. Jumlah segmen $1$ sama dengan jumlah segmen $0$ ditambah satu.

Dari observasi diatas, maka kita dapat menggunakan aturan perkalian untuk menggabungkan jawaban dari bagian pertama untuk segmen dari angka $0$ dan segmen dari angka $1$.

Kompleksitas waktu: $O(N\ log\ N)$.
> Faktor $O(log\ N)$ didapat dari penggunaan binary exponentiation ketika menghitung jawaban bagian pertama.

## D. Baim dan Jaim
### Pembahasan oleh Vincent Valentino Oei
Abridged description dari soal tersebut adalah:
Diberikan sebuah array $C$ berukuran $N$ yang berisi bilangan bulat ($|C_i| \leq 10^9$ dimana $C_i \in C$). Tentukan ukuran subarray terkecil dengan jumlah elemennya minimal $X$ ($|X|\leq 10^9$).

Dengan bruteforce kita dapat dengan mudah mendapatkan solusi kubik, dengan mencoba-coba setiap $i$ dan $j$ yang mungkin sehingga $j-i$ minimum dan $C_i+C_{i+1}+...+C_j \geq X$. Memang solusi ini benar, namun tidak akan mendapatkan poin apapun.

Untuk mendapatkan poin, kita perlu memikirkan solusi kuadratik terlebih dahulu. Yang paling mudah dioptimisasi dari cara sebelumnya adalah pada saat penjumlahan sebuah subarray, penjumlahan ini dapat dioptimisasi dengan penggunaan suatu data struktur seperti prefix sum sehingga penjumlahan hanya akan memakan waktu $O(1)$. Dengan optimisasi ini, anda akan mendapatkan poin pada subsoal 1.

> Terdapat beberapa cara untuk mendapatkan AC pada soal ini, yang akan dibahas di bawah hanyalah salah satu caranya.

Apa yang dapat kita optimisasi dari solusi kuadratik di atas? bruteforce pada $j$ atau $i$. Pada solusi ini kita akan hanya melakukan bruteforce pada $j$ sehingga kita perlu mencari sesuatu yang dapat menolong kita untuk mendapatkan $i$ yang optimal dalam kompleksitas yang rendah. Ternyata kita bisa menggunakan data struktur lain lagi, yakni _minimum segment tree_ dengan metode query _binary search on segment tree_.

Intinya adalah kita ingin mendapatkan $i$ yang paling kanan sehingga jumlah dari $C[i...j]$ lebih dari atau sama dengan $X$. Kita bisa mengisi segment tree dengan nilai-nilai yang sudah ada pada prefix sum kita, sehingga pada indeks ke $j$, kita hanya perlu mencari suatu $i$ sehingga $pref[i] \leq pref[j]-X$. Nah disinilah _binary search on segment tree_ berperan, jadi kita akan mengecek minimum dari branch kanan dahulu, apabila minimum pada branch kanan kurang dari $pref[j]-X$, maka telusuri ke dalam branch tersebut saja, jika tidak, telusuri ke branch kiri, namun jika keduanya tidak memenuhi prasyarat tersebut, maka jawabannya tidak ada. Metode ini akan membuat query berjalan dalam $O(log\ N)$, dengan bruteforce $j$ sebanyak $N$ kali.

Kompleksitas Waktu: $O(N\ log\ N)$

## E. Rencana Piranha
### Pembahasan oleh Pyqe
#### Diterjemahkan oleh Radhya Cahya Kusuma
Definisikan piranha tipe $1$ sebagai piranha dengan ukuran akhir $k$ sehingga terdapat paling sedikit satu piranha lain dengan ukuran akhir $k+1$, dan definisikan piranha tipe $2$ sebagai sisanya.

Bisa dilihat bahwa teman Anda bisa menghapus mulai dari piranha tipe $1$ terkecil, sehingga nilai $Q$ sama dengan banyaknya piranha tipe $1$. Semua piranha yang tersisa adalah piranha tipe $2$.

Bisa dilihat bahwa piranha dengan ukuran akhir sama pasti bertipe sama.

Misal kita telah memilih $M$ bilangan berbeda $W_1,W_2,…,W_M$​ dan ingin melakukan seminimum mungkin banyaknya pengubahan ukuran supaya untuk setiap $j$, terdapat paling sedikit satu piranha tipe $2$ yang berukuran akhir $W_j$​.

Untuk setiap $j$, tidak boleh ada piranha yang berukuran akhir $W_j+1$. Jika ada $i$ dan $j$ sehingga $W_i+1=W_j$​, maka jelas hal itu tidaklah mungkin. Selain itu, untuk setiap $j$, semua piranha yang berukuran awal $W_j+1$ harus diubah ukurannya. Semua piranha yang berukuran akhir $W_j$​ akan menjadi bertipe $2$, maka selalu lebih optimal untuk mengurangi ukuran semua piranha yang berukuran awal $W_j+1$ dengan $1$ daripada menambahnya.

Bisa didapat bahwa selalu lebih optimal untuk memilih $M$ bilangan tersebut sehingga untuk setiap $j$, terdapat paling sedikit satu piranha yang berukuran awal $W_j$​, maka pengubahan ukuran lain tidak diperlukan.

Bisa didapat juga bahwa melakukan pengubahan ukuran lain tidak akan mengurangi nilai $P+Q$.

Definisikan $f_q[x]$ sebagai banyaknya piranha yang berukuran awal xx.

Jika kita mengikuti strategi ini, untuk suatu array WW yang memungkinkan, bisa didapat bahwa:

- $P=f_q[W_1+1]+f_q[W_2+1]+…+f_q[W_M+1]$
- $Q=N−((f_q[W_1]+f_q[W_1+1])+(f_q[W_2]+f_q[W_2+1])+...+(f_q[W_M]+f_q[W_M+1]))$
- $P+Q=N−(f_q[W_1]+f_q[W_2]+…+f_q[W_M])$.

Maka, untuk mencari nilai $P+Q$ minimum yang mungkin, kita perlu mencari array $W$ sehingga:

Tidak ada $i$ dan $j$ sehingga $W_i+1=W_j$.
Nilai $f_q[W_1]+fq[W_2]+…+f_q[W_M]$ semaksimum mungkin.

Kita bisa menyelesaikan ini menggunakan DP. Definisikan $dp[x]$ sebagai nilai $f_q[W_1]+f_q[W_2]+...+f_q[W_M]$ maksimum yang mungkin untuk suatu array $W$ yang memungkinkan yang setiap elemennya tidak lebih dari $x$.

Kita bisa mendapatkan transisi $dp[x]=\text{max}⁡(dp[x−1],dp[x−2]+f_q[x])$.

Nilai $P+Q$ minimum yang mungkin sama dengan $N−dp[\text{MAX}]$.

Kompleksitas waktu: $O(\text{MAX})$.

## F. Zamrud untuk Semua
### Pembahasan oleh Radhya Cahya Kusuma

Apabila kita bisa melakukan konstruksi graf, soal ini menjadi sebatas mencari _shortest path_ dari node $1$ ke semua node yang ada. Permasalahan ini bisa diselesaikan dengan Algoritma Dijkstra.

Pembahasan di bawah menjelaskan bagaimana melakukan konstruksi graf dari testcase yang diberikan. Implementasi Dijkstra diserahkan kepada pembaca.

#### Subsoal 1 dan 2 (32 poin)
Bangun graf yang terdiri dari $N$ node.

Untuk setiap pasang $(U_i, V_i)$ penduduk yang saling kenal dengan $1 \leq i \leq K$, buat edge antara $U_i$ dan $V_i$ dengan bobot 0. Definisikan ini sebagai edge tipe $1$.

Untuk setiap pasang penduduk $i$ dan $j$ dengan $1 \leq i < j \leq n$, buat edge antara $i$ dan $j$ dengan bobot $|A_i - A_j|$. Definisikan ini sebagai edge tipe $2$.

Kompleksitas: $O((N^2 + K) \log(N^2+K))$.
dengan log berasal dari Dijkstra.

#### Full Solution
Untuk setiap pemilihan 3 penduduk $i, j, k$ yang memenuhi $A_i < A_j < A_k$ dengan $1 \leq i,j,k \leq n$, perhatikan bahwa jarak terdekat antara $i$ dan $k$ bisa dipecah menjadi jarak antara $i$ dan $j$ ditambah jarak antara $j$ dan $k$.

Oleh karena itu, kita hanya perlu menghubungkan $i$ dan $j$ dengan edge tipe $2$ apabila $A_i$ dan $A_j$ bersebelahan. Formalnya, kita menghubungkan penduduk $i$ dan $j$ jika **tidak** terdapat $k$ yang memenuhi $A_i < A_k < A_j$ untuk $1 \leq i,j,k \leq n$.

Kompleksitas: $O((N+K) \log (N+K))$

## G. Crash Loyale
### Pembahasan oleh Joshua James

#### Subsoal 1 (8 poin)

Untuk kasus $N = 1$, kartu yang mungkin terambil hanyalah kartu-kartu yang berada pada dek tangan awal. Sehingga, nilai harapan dari total elixir yang akan terpakai bisa didapatkan dari penjumlahan nilai elixir pada kartu awal yang dibagi dengan 4.

Kompleksitas: $O(1)$

#### Subsoal 2 (18 poin)

Sama seperti subsoal 1, hanya saja karena kasus ini total elixir yang terpakai belum tentu habis dibagi 4. Dengan menggunakan Fermat Little Theorem, kita bisa menghitung nilai dari $\frac{totalelixir}{4}$ $\mod 10^9 + 7$ menjadi $totalelixir \times 4^{10^9 + 5}$ yang dapat dihitung menggunakan modular exponentiation.

Kompleksitas: $O(log(mod))$.

#### Subsoal 3 (25 poin)

Secara totla, paling banyak ada $8^5$ kemungkinan urutan yang mungkin. Karena nilai tersebut sangat kecil, kita dapat mengecek untuk setiap kemungkinan apakah kemungkinan tersebut valid atau tidak. Jika valid, makaa kita akan menghitung jumlah elixir yang akan terpakai untuk kemungkinan tersebut.

Kompleksitas: $O(8^N \times N)$

#### Subsoal 4 (13 poin)

Perhatikan bahwa pada kasus ini, untuk setiap ronde, jumlah elixir yang digunakan pasti sama. Maka dari itu, total elixir yang digunakan pasti ada sebanyak $A_i \times N$.

Kompleksitas: $O(1)$

#### Subsoal 5 (36 poin)

Pertama-tama, kita dapat merepresentasikan sebuah dek tangan sebagai sebuah bitmask yang terdiri dari $8$ bit dengan bit ke-$i$ bernilai $1$ jika kartu ke-$i$ sedang berada di dek tangan, dan $0$ jika sebaliknya.

Kita dapat mendefinisikan $DP[i][j]$ sebagai nilai harapan pemakaian elixir sampai ronde ke-$i$, serta dek tangan setelah ronde ke-$i$ bernilai $j$. Serta $prob[i][j]$ adalah probabilitas kita memiliki dek tangan bernilai $j$ setelah ronde ke $i$.

Didefinisikan pula sebuah bitmask $x$ sebagai substitute dari sebuah bitmask $y$ jika bit yang menyala pada hasil $x xor y$ berjumlah tepat 2 bit. Sebagai contoh, jika $x = (10110010)_2$ dan $y = (10011010)_2$ maka $x$ merupakan substitute dari $y$.

Nilai $prob[i][j]$ dapat dihitung menggunakan rumus $prob[i][j] = \sum_{j'}{\frac{1}{16}{\times prob[i - 1][j']}}$ dimana $j'$ merupakan substitute dari $j$. Ini bisa didapatkan dari probabilitas nilai $j'$ ber-transisi menjadi $j$ dalam satu ronde adalah $\frac{1}{16}$.

Dari sini, kita juga dapat melihat bahwa saat bertransisi dari mask $j'$ menjadi $j$, terdapat $1$ buah bit yang menyala pada $j'$ dan mati pada $j$. Misalkan bit tersebut merupakan bit ke-$k$, maka artinya pada saat ronde ke-$i$, kita menggunakan kartu dengan indeks $k$.

Dengan begitu, kita dapat merumuskan $DP[i][j] = \sum_{j'}{\frac{1}{16}{\times A_k \times prob[i - 1][j'] + DP[i - 1][j']}}$. Dimana $j'$ merupakan substitute dari $j$.

Jawaban bisa didapatkan dari $\sum_{mask}{DP[N][mask]}.

Perhatikan bahwa jumlah bitmask yang valid hanya ada sebanyak $_8C_4 = 70$ sehingga total transisi untuk tiap ronde ada sebanyak $70 \times 4^2$.

Kompleksitas: $O(N\times 70 \times 4^2)$

## H. Penyebaran Hoaks
### Pembahasan oleh Vincent Valentino Oei

Pertama, perhatikan bahwa terdapat tepat $N$ pengguna situs sosial media dan terdapat tepat $N$ hari yang akan dilalui. Sehingga sudah pasti bahwa suatu connected component yang mempunyai setidaknya 1 penyebar hoaks pada awalnya akan berakhir dengan setiap componentnya menjadi penyebar hoaks, karena pada kasus paling buruk sekalipun, selama suatu connected component masih belum terkena hoaks sepenuhnya, maka akan ada setidaknya 1 orang penyebar hoaks baru untuk setiap hari $i$ untuk $1 < i \leq N$.

Dari observasi tersebut maka kita dapat melakukan line sweep terhadap jam-jam dimana pengguna-pengguna tersebut online dan mengganggap setiap pengguna sebagai component, sehingga jika ada $2$ atau lebih pengguna yang online bersamaan, maka kita akan menyatukan mereka ke dalam suatu connected component. Disjoint Set Union merupakan salah satu data struktur yang dapat digunakan untuk penggabungan ini.

Kompleksitas waktu: $O(N\ log\ N)$

## I. Regulasi Penerbangan Covid
### Pembahasan oleh Yomori Achiza
Misalkan $cntDepan[i]$ dan $cntBelakang[i]$ adalah banyak orang yang $i$ lewati menuju pintu depan dan belakang. Untuk mengoptimalisasi perhitungan, kita bisa menggunakan Binary Indexed Tree atau Segment Tree untuk penumpang di kolom C dan D.

Perhatikan bahwa $By$ hanya dipengaruhi oleh jumlah orang yang berada di ruang isolasi di akhir. Misalkan, setelah $M$ orang keluar, di ruang isolasi depan terdapat $P$ orang di depan dan $Q$ orang di belakang, maka nilai $By = (1+2+...+(P-1)) \times B + (1+2+...+(Q-1)) \times B$.

Sehingga kita bisa menganggap semua orang ke depan terlebih dahulu. Kemudian dengan greedy kita pindahkan penumpang dengan selisih $cntBelakang[i]-cntDepan[i]$ terkecil ke belakang.

Bruteforce banyak penumpang ke pintu belakang $(0 \leq i \leq M)$. $Sum$ menyimpan total penumpang yang dilewati. Untuk setiap i, $Sum$ ditambahkan dengan $cntBelakang[i]-cntDepan[i]$. Maka total nilai ketidaknyamanannya adalah $sum \times A +({deret}(i)+{deret}(M-i) \times B$. Nilai ketidaknyaman minimum adalah jawabannya.

Kompleksitas $O(M\ log\ N)$

## J. Pengiriman Satu Hari
### Pembahasan oleh Joshua James

Kita notasikan $\\\\text{query}(x)$ sebagai peserta mengeluarkan $x$, dan $\\\\text{get}(x)$ sebagai peserta membaca hasil dari $\\\\text{query}(x)$ (setidaknya satu hari setelahnya), dengan kita definisikan:

- $\\\\text{get}(x)=-1$ jika jawabannya lebih kecil dari $x$.
- $\\\\text{get}(x)=1$ jika jawabannya lebih besar dari $x$.
- $\\\\text{get}(x)=0$ jika jawabannya $x$.

Kita notasikan $\\\\text{query}(\\\\\varnothing)$ sebagai pertanyaan sembarang, yang kita tidak peduli terhadap hasilnya.

Kita notasikan "interval saat ini" sebagai interval $[l,r]$ yang kita _yakin_ bahwa ukuran sepatunya ada di interval ini. Awalnya, interval saat ini adalah $[1,N]$, dan dengan bertanya, kita akan memperkecil interval ini.

Di semua subsoal kecuali subsoal 1 dan subsoal 7, batas untuk $T$ bersifat optimal; tidak ada strategi yang bisa mengidentifikasikan semua kemungkinan ukuran sepatu yang menggunakan lebih sedikit dari $T$ pertanyaan dalam kasus terburuknya. Untuk subsoal 7, banyaknya pertanyaan yang optimal adalah $44$ (yang diperlukan untuk mendapatkan poin penuh).

#### Subsoal 1

Kita bisa lakukan $\\\\\text{query}(1)$, $\\\\\text{query}(2)$, $\\\text{query}(3)$, $\\\\\text{query}(4)$, $\\\text{query}(5)$, dan $\\\\\text{query}(\\\\\varnothing)$. Karena kita mencoba semua ukuran sepatu yang mungkin, salah satu hasil dari $\\\\text{get}$ adalah $0$.

#### Subsoal 2

Kita bisa coba kasus-kasusnya di kertas untuk mendapatkan intuisi solusinya.

Pertama, seperti _binary search_, gerakan pertama yang optimal secara intuitif adalah melakukannya di suatu tempat di tengah. Namun, ternyata jika pertanyaan pertama kita adalah $\\\\\text{query}(4)$, kita akan terpaksa harus menggunakan setidaknya $6$ pertanyaan.

Ternyata salah satu cara optimal adalah jika pertanyaan pertama adalah $\\\\text{query}(3)$, lalu diikuti dengan $\\\\\text{query}(5)$. Tergantung dengan jawaban $\\\\\text{get}(3)$, kita akan rekursi ke interval $[1,2]$ (yang bisa kita selesaikan dengan mudah dalam $3$ pertanyaan), atau interval $[4,7]$.

Namun, jika kita dapat kasus kedua, perhatikan bahwa kita punya satu $\\\\\text{query}(5)$ yang "_pending_" di interval $[4, 7]$. Jika kita ikuti dengan $\\\\\text{query}(6)$, tergantung $\\\\\text{get}(5)$, kita akan rekursi ke $[4, 4]$ (yang bisa diselesaikan dalam $2$ pertanyaan), atau kita rekursi ke $[6, 7]$ (yang butuh $3$ pertanyaan; namun, perhatikan bahwa kita punya $\\\\\text{query}(6)$ yang "_pending_", maka kita hanya perlu $2$ pertanyaan tambahan).

#### Solusi Parsial

Ada banyak sekali cara untuk mendapat skor parsial untuk subsoal 7, yang hanya akan kita bahas sedikit.

Salah satu kemungkinan untuk mendapatkan banyaknya pertanyaan yang kurang optimal adalah melakukan _binary search_ biasa. Perhatikan bahwa kita bisa gunakan dua pertanyaan untuk mendapatkan jawaban yang pasti. Lebih spesifiknya, dengan melakukan $\\\\\text{query}(x)$ dan $\\\\\\text{query}(\\\\\varnothing)$, kita bisa mendapatkan hasil $\\\\\text{get}(x)$, yang memungkinan _binary search_ dalam $2 \\\\\lceil \\\\\log N \\\\\rceil$ pertanyaan.

Ada strategi lain juga; contohnya, kita bisa lakukan "_ternary search_" dengan $3$ pertanyaan ($\\\\\text{query}(m_1)$, $\\\\\text{query}(m_2)$, $\\\\\text{query}(\\\\\varnothing)$ dengan $m_1,m_2$ merupakan titik-titik pemisahannya) untuk memisahkan interval saat ini menjadi tiga. Kita bisa optimisasi ini lebih jauh dengan mengatur rasio ukuran tiga intervalnya, dengan memerhatikan bahwa kita bisa $\\\\\text{get}(m_1)$ tepat setelah menanyakan $\\\\\text{query}(m_2)$, yang berpotensi menghemat satu pertanyaan tambahan (karena jika $\\\\\text{get}(m_1)=-1$, kita tidak perlu $\\\\\text{query}(\\\\\varnothing)$).

Dalam bagian-bagian berikutnya setelah bagian ini, kita hanya akan menjelaskan bagaimana cara mendapat banyaknya pertanyaan yang optimal, yang tergantung dari $N$ bernilai lebih kecil sama dengan suatu batas. Kita bisa gabung cara-cara optimal ini dengan cara solusi parsial dengan strategi dua langkah berikut:

* Jika interval saat ini besar, gunakan solusi parsial.
* Jika interval saat ini cukup kecil untuk solusi optimal bekerja, kita gunakan solusi optimal.

#### Subsoal 3

Karena adanya pertanyaan terakhir yang tidak terjawab, kelihatannya rumit untuk membuat strategi secara manual untuk $N$ yang besar. Oleh karena itu, kita coba gunakan _dynamic programming_ untuk menyimpan _state_ pertanyaan-pertanyaan kita saat ini.

Kita definisikan $\\\\\text{dp}_1(l, r, x)$ sebagai banyaknya pertanyaan minimum yang dibutuhkan ketika interval saat ini adalah $[l, r]$, dan pertanyaan terakhir yang belum terjawab adalah $x$ (awalnya, $x = \\\\\varnothing$). Kita bisa "transisi" ke status baru dengan menanyakan pertanyaan baru. Misalnya kita menanyakan pertanyaan baru $m \\\\\in [l, r]$, lalu kita dapatkan nilai $\\\\\text{get}(x)$, yang mengakibatkan:

* Kasus 1: $\\\\text{get}(x) = 0$, maka kita menggunakan $1$ pertanyaan (menanyakan $\\\\\text{query}(m)$).
* Kasus 2: $\\\\text{get}(x) = -1$, maka kita menggunakan $1 + \\\\\text{dp}\_1(l, \\\\min(r, x-1), m)$ pertanyaan.
* Kasus 3: $\\\\\text{get}(x) = 1$, maka kita menggunakan $1 + \\\\\text{dp}\_1(\\\\\max(l, x+1), r, m)$ pertanyaan.

Namun, kita tidak tahu nilai dari $\\\\\text{get}(x)$. Oleh karena itu, untuk suatu nilai tetap $m$, _pada kasus terburuk_, kita akan butuh $1 + \\\\\max(\\\\\text{dp}\\_1(l, \\\\\min(r, x-1), m), \\\\\text{dp}\\_1(\\\\\max(l, x+1), r, m))$ pertanyaan.

Yang bisa kita kontrol adalah pemilihan $m$; oleh karena itu, kita akan coba semua kemungkinan $m \\\\\in [l, r]$ dan pilih yang minimum dari mereka.

Ada $O(N^3)$ status DP, dan di setiap status, kita butuh $O(N)$ untuk transisinya, maka kompleksitas waktu keseluruhannya adalah $O(N^4)$.

Setelah menghitung nilai-nilai DP-nya, kita bisa konfirmasi bahwa $\\\\\text{dp}\\_1(1, 50, \\\\\varnothing) = 9$, yang memang merupakan batas banyaknya pertanyaan. Kita bisa "_backtrack_" dan simulasikan interaksinya dengan cara berikut:

* Misalnya kita saat ini sedang di status $(l, r, x)$. Kita pilih pilihan $m$ yang meminimalisasikan $\\\\\text{dp}\\_1(l, r, x)$, dan tanyakan pertanyaan itu.
* Tergantung $\\\\\text{get}(x)$, kita rekursi ke tiga kasus yang dijelaskan di atas.

Berikut adalah beberapa trik implementasi yang mungkin:

* Kita definisikan $\\\text{dp}_1(l, r, x)$ seperti di atas, untuk menghitung minimum banyaknya pertanyaan yang dibutuhkan.
* Kita definisikan $\\\\\text{choice}_1(l, r, x)$ sebagai fungsi yang mengembalikan nilai $m$ yang optimal yang meminimalisasikan $\\\\\text{dp}_1(l, r, x)$.
* Kita definisikan $\\\\\text{interaction}(l, r, x)$ sebagai fungsi yang berinteraksi dengan program juri, dengan menggunakan $\\\\\text{choice}_1(l, r, x)$ untuk mendapatkan pertanyaan-pertanyaannya. Lebih spesifiknya, dalam $\\\\\text{interaction}(l, r, x)$ kita akan mengeluarkan $\\\\\text{choice}_1(l, r, x)$, lalu menggunakan nilai $\\\\\text{get}(x)$ untuk rekursi ke salah satu dari tiga kasus yang dijelaskan di atas.

Kompleksitas waktu: $O(N^4)$

#### Subsoal 4

Mari kita buat beberapa optimisasi pada status DP-nya:

* Jika $x \\\\\not\\\\\in [l, r]$, kita bisa saja jadikan $x := \\\\\varnothing$ dan itu tidak akan mengubah jawaban.
* Nilai $l$ dan $r$ yang tepatnya tidak begitu berpengaruh; kita bisa gantikan $\\\\\text{dp}_1(l, r, x)$ dengan $\\\\\text{dp}_1(1, r - (l - 1), x - (l - 1))$ karena keduanya mempunyai nilai yang sama, dengan "menggeser" beberapa nilai ke kiri.

Setelah menerapkan hal-hal di atas, kita hanya akan mempunyai $O(N^2)$ _state_ yang penting pada DP-nya.

Perhatikan bahwa kita bisa menghindari mengimplementasi ulang $\\\\\text{interaction}(l, r, x)$ hanya dengan memodifikasi sedikit $\\\\\text{choice}_1(l, r, x)$. Jika $l > 1$, kita buat $\\\\\text{choice}_1(l, r, x)$ mengembalikan $(l - 1) + \\\text{choice}_1(1, r - (l - 1), x - (l - 1))$.

Kompleksitas waktu: $O(N^3)$

#### Subsoal 5

Tinjau pertanyaan pertama dan kedua $\\\\\text{query}(m_1)$ dan $\\\text{query}(m_2)$. WLOG, asumsikan $m_1 < m_2$.

Perhatikan bahwa jika $\\\text{get}(m_1)=-1$, kita tidak peduli terhadap nilai $m_2$, dan kita akan langsung rekursi ke $\\\text{dp}_1(l, m_1-1, \\\varnothing)$. Oleh karena itu, kita akan definisikan DP kita sebagai berikut.

Kita definisikan $\\\text{dp}_2(l, r, f)$ ketika interval saat ini adalah $[l, r]$, dan kita punya $f \\\in \\\{0,1\\\}$ pertanyaan "gratis". Di sini, sebuah pertanyaan gratis berarti kita sudah memperhitungkan _cost_ pertanyaan itu, tetapi belum menentukan apa pertanyaan itu. Kita juga definisikan $\\\text{choice}_2(l, r, f)$ serupa dengan $\\\text{choice}_1$.

Dalam contoh sebelumnya, kita awalnya mulai dari $\\\text{dp}_2(1, N, 0)$. Kita bayar $2$ pertanyaan untuk melakukan $\\\text{query}(m_1)$ dan $\\\text{query}(m_2)$; namun, ketika menetapkan nilai $m_1$, kita biarkan nilai $m_2$ sebagai belum ditentukan. Lalu, setelah dua pertanyaan itu, jika $\\\text{get}(m_1)=-1$, kita akan rekursi ke $\\\text{dp}_2(1, m_1-1, 0)$ (karena nilai $m_2$ dan $\\\text{get}(m_2)$ tidak relevan). Jika $\\\text{get}(m_1)=1$, kita rekursi ke $\\\text{dp}_2(m_1+1, N, 1)$, karena kita punya satu pertanyaan gratis (yaitu, kita bisa tetapkan $m_2$ dengan nilai berapa pun di $[m_1+1, N]$ yang kita mau).

Oleh karena itu, transisi untuk _dynamic programming_ kita sekarang adalah:

* Tetapkan nilai $m_1 \\\in [l, r]$. Perhatikan bahwa pertanyaan ini memiliki _cost_ $(1-f)$.
* Lalu, kita punya dua pilihan: kita tetapkan $m_2 < m_1$ atau kita tetapkan $m_1 < m_2$. Pertanyaan $\\\text{query}(m_2)$ yang belum ditentukan ini memiliki _cost_ $1$.
* Dengan menganggap $m_1 < m_2$, kita akan rekursi ke $\\\max(\\\text{dp}_2(l, m_1-1, 0), \\\text{dp}_2(m_1+1, r, 1)$. Kasus yang lainnya serupa.

Sekali lagi, menggunakan trik dari solusi subsoal 4, kita bisa hitung nilai-nilai DP hanya untuk $l=1$. Dengan cara ini, kita mengurangi _state_ kita menjadi $O(N)$, dan setiap transisi memakan waktu $O(N)$ (untuk mengiterasikan nilai $m_1$).

Tetapi sekarang, ada sedikit masalah saat berinteraksi dengan juri, karena $m\_2$ tidak ditentukan. Mari kita lihat $\\\text{choice}_1(l, r, x)$ dan lihat kasusnya. Perhatikan bahwa kita mengasumsikan $l=1$.

* Jika $x = \\\varnothing$, kita kembalikan $\\\text{choice}_2(l, r, 0)$ karena kita tidak punya pertanyaan "gratis" yang _pending_.
* Selain itu, anggap $m_1 := x$. Kita punya pilihan untuk membuat $m_2 < m_1$ atau $m_2 > m_1$ untuk meminimalisasi $\\\text{dp}_1(l, r, x)$.
* Jika $m_2 < m_1$, maka nilainya $1 + \\\max(\\\text{dp}_2(1, m_1 - 1, 1), \\\text{dp}_2(m_1 + 1, r, 0))$.
* Jika $m_2 > m_1$, maka nilainya is $1 + \\\max(\\\text{dp}_2(1, m_1 - 1, 0), \\\text{dp}_2(m_1 + 1, r, 1))$.
* Misalkan $m\_1 < m\_2$ adalah pilihan optimal untuk meminimalisasi $\\\text{dp}_1(l, r, x)$. Maka nilai $m_2$ yang optimal adalah $\\\text{choice}_2(m_1 + 1, r, 1)$. Kasus yang lainnya serupa.

Oleh karena itu, kita bisa mengimplementasikan $\\\text{choice}_1$ secara mudah hanya dengan mengetahui $\\\text{dp}_2$ dan $\\\text{choice}_2$, sehingga kita bisa gunakan implementasi lama untuk $\\\text{interaction}(l, r, x)$.
Kompleksitas waktu: $O(N^2)$

#### Subsoal 6

Kita butuh cara untuk mengoptimisasi _dynamic programming_ kita lebih jauh. Kita tahu bahwa banyaknya pertanyaan itu memiliki batas atas $2 \\\lceil \\\log N \\\rceil$ (menurut solusi parsial kita yang sebelumnya dibahas), maka sangat sedikit. Mungkin kita bisa gunakan fakta ini?

Kita sekarang akan coba "memutar" _state_ DP kita. Kita definisikan $\\\text{dp}_3(q, f)$ sebagai nilai maksimum sehingga $\\\text{dp}_2(1, \\\text{dp}_3(q, f), f) \\\leq q$. Perhatikan bahwa dalam konstruksinya, hanya ada $O(\\\log N)$ _state_ di formulasi $\\\text{dp}_3$. Kita juga bisa mendefinisikan $\\\text{choice}_3(q, f)$ dengan cara serupa.

Untuk mempersingkat, _base case_\-nya diserahkan sebagai latihan untuk pembaca. Transisi untuk $\\\text{dp}_3(q,f)$ adalah:

* Jika $f = 0$, kita akan membayar dua pertanyaan untuk $\\\text{query}(m_1)$ dan $\\\text{query}(m_2)$, dan misalkan $m_1 < m_2$. Secara total kita bisa identifikasikan sebuah interval dengan panjang $\\\text{dp}_3(q, 0) = \\\text{dp}_3(q-2,0) + 1 + \\\text{dp}_3(q-2, 1)$, karena:
* Jika $\\\text{get}(m_1)=-1$, kita bisa identifikasikan jawabannya dari interval dengan panjang $\\\text{dp}_3(q-2, 0)$. 
* Jika $\\\text{get}(m_1)=0$, kita bisa identifikasikan jawabannya dari interval dengan panjang $1$ (yaitu, $m_1$ itu sendiri). Perhatikan bahwa ini mengimplikasikan bahwa $\\\text{choice}_3(q, f) = \\\text{dp}_3(q-2, 0) + 1$.
* Jika $\\\text{get}(m_1)=1$, kita bisa identifikasikan jawabannya dari interval dengan panjang $\\\text{dp}_3(q-2, 1)$ (karena kita biarkan $m_2$ sebagai belum ditentukan).
* Jika $f=1$, kita hanya membayar satu pertanyaan tambahan untuk $\\\\text{query}(m\_2)$, dan menggunakan pertanyaan gratisnya untuk $\\\\\text{query}(m_1)$. Oleh karena itu, secara total, kita bisa mengidentifikasikan interval dengan panjang $\\\text{dp}_3(q, 1) = \\\text{dp}_3(q-1,0) + 1 + \\\text{dp}_3(q-1, 1)$.

Namun, $\\\text{dp}_3(q, f)$ tidak begitu berguna sendirian, karena panjang intervalnya tidak selalu $\\\text{dp}_3(q, f)$. Mari kita hubungkan kembali ke $\\\text{dp}_2$. Perhatikan bahwa nilai $\\\text{dp}_2(l, r, f)$ adalah nilai $q$ terkecil sehingga $\\\text{dp}_3(q, f) \\\geq r - l + 1$.

Oleh karena itu, kita bisa menghitung $\\\text{dp}_2(l, r, f)$ untuk nilai-nilai $l,r,f$ sembarang dalam $O(\\\log N)$. Kita kemudian bisa mencoba semua pemilihan $m_1 \\\in [l, r]$ untuk menentukan nilai $\\\text{choice}_2(l, r, f)$ dalam $O(N \\\log N)$.

Kompleksitas waktu: $O(N \\\log N)$

#### Subsoal 7

Perhatikan bahwa kita tidak peduli jika panjang intervalnya tidak sama dengan $\\\\\text{dp}_3(q, f)$. Perhatikan bahwa $\\\text{dp}_3(q, f)$ selalu lebih besar sama dengan panjang dari interval saat ini menurut definisinya. Oleh karena itu kita bisa saja perpanjang interval saat ini secara artifisial menjadi $\\\text{dp}_3(q, f)$; contohnya, jika interval sekarang adalah $[l, r]$, kita tetapkan $r := l - 1 + \\\text{dp}_3(q, f)$.

Namun, jika kita perpanjang interval saat ini secara artifisial dengan cara ini, maka bisa jadi $r > N$. Kita bisa modifikasi implementasi kita untuk mengatasi ini, karena kita tahu $\\\text{get}(x) = -1$ jika $x > N$. Kita bisa saja memilih untuk tidak mengeluarkan apa pun ke juri untuk $\\\text{query}(x)$ jika $x > N$.

Oleh karena itu, sekarang kita bisa berasumsi bahwa panjang interval saat ini selalu sama dengan $\\\text{dp}_3(q, f)$. Maka kita bisa menggunakan nilai $\\\text{choice}_3(q, f)$ sebagai nilai $m_1$ atau $m_2$ yang optimal.

Kompleksitas waktu: $O(\\\log N)$

#### Solusi Alternatif

Tanpa mendapatkan transisi $\\\text{dp}_3(q,f)$ secara eksplisit, kita bisa menghitungnya dengan mencari nilai $r$ maksimum sehingga $\\\text{dp}_2(1, r, f) \\\leq q$.

Jika kita mencetak nilai-nilai $\\\text{dp}_3(q,0)$, ternyata $\\\text{dp}_3(q,0) = F_q - 1$ dengan $F_q$ merupakan bilangan Fibonacci ke-$q$ $1,2,3,5,8,\\\dots$.

Dengan mengetahui ini, kita bisa coba membuat strategi yang melibatkan bilangan Fibonacci ini. Misalkan $N = F\_Q - 1$.

* Perhatikan bahwa $F\_Q - 1 = (F\_{Q-2}-1)+1+(F\_{Q-1}-1)= (F\_{Q-2} - 1) + 1 + (F\_{Q - 3} - 1) + 1 + (F\_{Q-2} - 1)$.
* Kita bisa menanyakan $m_1 := F\_{Q-2}$ dan $m\_2 := F\_{Q-2} + F\_{Q-3}$.
* Jika $\\\text{get}(m_1) = -1$, kita bisa rekursi ke interval $[1, F_{Q-2}-1]$ dengan $2$ pertanyaan.
* Jika $\\\text{get}(m_1) = 1$, kita bisa rekursi ke interval $[F_{Q-2}+1, F_Q - 1]$ dengan panjang $F_{Q-1}-1$. Perhatikan bahwa $m_1'$ di interval baru ini adalah titik $m_2$ yang sudah kita tanyakan, maka kita bisa gunakan pertanyaan gratisnya. Maka kasus ini menggunakan $1$ pertanyaan.

Oleh karena itu, dengan $k \\\in \\\{1,2\\\}$ pertanyaan, kita bisa berpindah dari sebuah interval dengan panjang $F_{Q}-1$ ke interval dengan panjang $F_{Q-k}-1$. Ini menunjukkan bahwa strategi Fibonacci ini menghasilkan batas bawah untuk $\\\text{dp}_3$; yaitu, $\\\text{dp}_3(q,0) \\\geq F_q - 1$.

Solusi lain yang menggunakan observasi Fibonacci ini adalah dengan tidak melakukan prekomputasi Fibonacci sama sekali, tetapi dengan membagi intervalnya menggunakan _golden ratio_ $\\\phi=\\\dfrac{1+\\\sqrt5}{2}$ (rasio antara bilangan Fibonacci). Untuk interval dengan panjang $N$, kita bagi menjadi tiga bagian dengan panjang kira-kira $\\\dfrac{N}{\\\phi^2}$, $\\\dfrac{N}{\\\phi^3}$, dan $\\\dfrac{N}{\\\phi^2}$ dengan memilih $m_1$ dan $m_2$ kira-kira $\\\dfrac{N}{\\\phi^2}$ dan $\\\dfrac{N}{\\\phi}$ secara berturut-turut, kemudian lanjutkan seperti solusi di atas.

Sisi buruk dari menemukan solusi ini adalah kita belum membuktikan bahwa ini adalah strategi optimal.

Kompleksitas waktu: $O(\\\log N)$

#### Bonus

Bisakah Anda menyelesaikan soal ini jika _delay_\-nya adalah $M$ hari, bukan satu hari, untuk $M \\\geq 2$?