---
# System prepended metadata

title: Pembahasan Tebak Barisan

---

# Pembahasan Tebak Barisan
## Subsoal 1
Coba setiap permutasi yang mungkin. Jika permutasi $A$ yang dicoba mengembalikan $0$, maka dapat disimpulkan bahwa $P_{A_0} = 0, P_{A_1} = 1, ..., P_{A_{N - 1}} = N - 1$

## Subsoal 2 (8 poin)
Perhatikan bahwa kita dapat menggunakan query untuk membandingkan antara dua elemen $P_x$ dan $P_y$ dengan melakukan query ```? 2 x y```. Jika kita bisa membuat array $A$ sehingga $P_{A_0} < P_{A_1} < ... < P_{A_{N - 1}}$, maka kita bisa mendapatkan nilai $P$ dengan mudah. Untuk mengurutkan $A$ kita dapat menggunakan algoritma sorting $O(N^2)$ ataupun algoritma sorting yang disediakan oleh C++.

## Subsoal 2 (27 poin)
Mengimplementasikan sorting dengan menggunakan merge sort sendiri akan menjamin menggunakan $N\text{log}N$ query. Dengan itu, kita bisa mengerjakan dengan cara yang sama seperti subsoal sebelumnya.

### Subsoal 2 (Suboptimal Full Solution)
Perhatikan bahwa kita hanya menggunakan query untuk membandingkan 2 elemen yang berbeda. Kita bisa menggunakan beberapa barisan untuk mencari perbandingan beberapa elemen yang berbeda dengan cepat. 

Misalnya, jika kita ingin mencari nilai $P_{A_z}$ relatif terhadap $P_{A_x}$ dan $P_{A_y}$ dengan syarat $P_{A_x} < P_{A_y}$. Kita bisa menggunakan urutan query berikut:
<pre>
A<sub>x</sub> A<sub>z</sub> A<sub>y</sub> A<sub>x</sub> A<sub>z</sub>
</pre>

Ada 3 nilai kembalian yang mungkin dari query:
- Jika nilai kembalian ```1```, maka $P_{A_x} < P_{A_z} < P_{A_y}$.
- Jika nilai kembalian ```2```, maka $P_{A_x} < P_{A_y} < P_{A_z}$.
- Jika nilai kembalian ```3```, maka $P_{A_z} < P_{A_x} < P_{A_y}$.

### Subsoal 2 (Full Solution)
Kita dapat memeriksa posisi suatu elemen $P_y$ di suatu barisan $P_{A_0}, P_{A_1}, ..., P_{A_{x - 1}}$ dengan syarat $P_{A_0} < P_{A_1} < ... < P_{A_{x - 1}}$.

Query yang dapat digunakan adalah sebagai berikut:
<pre>
A<sub>0</sub> y A<sub>1</sub> A<sub>0</sub> y A<sub>2</sub> A<sub>0</sub> y ... A<sub>x - 1</sub> A<sub>0</sub> y 
</pre>

Dengan menggunakan query tersebut ada $x + 1$ nilai kembalian query yang mungkin.
- Jika nilai kembalian adalah $x - 1$, maka $P_y < P_{A_0}$.
- Untuk setiap kemungkinan lain, maka $P_y > P_{A_{b - x + 1}}$ dimana $b$ adalah nilai kembalian query.

Dari situ kita dapat mengkonstruksi array $A$ hingga berukuran $N$ dengan menggunakan $N - 1$ query.