# Editorial Simulasi OSN 2022 - 1C
## by kokocoder (unofficial)

---

<center><h3>Soal 1C</h3></center>

**Observasi 1**
(dapet dari subtask yang $N$ nya 0)

Kita anggap dulu benteng bentengnya cuma ada di garis horizontal (that is, semua benteng yang ada merupakan benteng vertikal)

Kita sebut posisi benteng benteng ini ada di $x_1, x_2, ..., x_M$


Maka sebenernya menebak benteng disini sama aja kayak nebak titik titik di sumbu $x$ itu ada dimana aja

Let's say kita punya suatu fungsi $solve(L, R)$ buat kita menebak posisi benteng benteng yang ada di antara $L..R$ (inklusif)

Nah idenya adalah, kita bisa tembak ~~orang yang kamu suka~~ titik tengah di antara $L$ sampai $R$ (simply $(L+R)/2$)

---

**Kemungkinan 1 : gak ada benteng di titik yang kita tembak**

Misal kalo disini kita tembak $10$, berarti grader bakal balikin jawaban $3$. Nah masalahnya kita gak tau nih bentengnya ada di $7$ atau $13$, tapi satu hal yang pasti :

***Pasti terdapat benteng diantara $x=7$ atau $x=13$***

Jadi nanti kita akan rekursi ke :

$solve(0, 7)$ dan $solve(13, 20)$

Jadi secara formal, kemungkinan pertama saat bertanya adalah :

**jika $d = ask(mid, 0)$ dan $d>0$, maka kita akan rekursi ke :**

- $solve(L, mid-d)$ dan
- $solve(mid+d, R)$

**Kemungkinan 2 : Ada benteng di titik yang kita tembak**

Sekarang misalkan kita cari titik di tengah tengah $solve(13, 20)$, berarti :


disini $d = ask(mid, 0) = 0$ yang artinya ada benteng di posisi $x = mid$

Artinya, kita udah berhasil nebak satu posisi benteng. Nah sekarang kita tinggal rekursi aja ke :

- $solve(L, mid-1)$ dan
- $solve(mid+1, R)$

dan kita tinggal melakukan hal yang sama

Dengan cara ini kita bisa dapat **posisi benteng-benteng yang ada di sumbu $x$**

Kira kira pertanyaan yang dibutuhin buat ngelakuin operasi ini adalah $2M$ dimana $M$ itu banyaknya benteng

---

**Observasi 2**
Nah tapi sekarang gimana kalooooo.... bentuk bentengnya 2D ~~kayak waifu~~ ?


Kita bisa mengadopsi strategi yang mirip kayak strategi pertama. Cuma kali ini, instead of kita bertanya di $(mid, 0)$, kita bakal tanya di $(mid, mid)$

Kita liat dari gambar di bawah ini :


... eh salah gambar


Nah dari gambar ini, kita punya range pencarian dari $(0, 10)$

Idenya sama, kita tembak lagi titik tengah (mid) yang ada di posisi $(5,5)$


**Kemungkinan 1 : Ada benteng di posisi yang kita tembak**

Nah disini grader bakal kasih jawaban 0

Tapi sekarang kita punya pertanyaan :
Nah kalo kayak gini bentengnya bisa di dua kemungkinan :
$x=5$ atau $y=5$
tapi kan kita gak tau jawabannya? Gimana dong?

Nah jawabannya kita "tampung" dulu ke sebuah himpunan $Q$. Sebut aja $Q$ ini adalah himpunan berisi titik titik yang mungkin menjadi posisi benteng

Secara formal himpunan $Q$ ini bakal berisi titik titik $q_1, q_2, ..., q_{|Q|}$ dimana untuk setiap $i$, terdapat benteng di $x = q_i$ atau $y = q_i$ (bisa juga dua duanya), saat ini kita belom tau tapi $q_i$ itu termasuk dimana

Jadi kalo kita tembak di titik $(mid, mid)$ dan ada bentengnya, berarti next kita rekursi ke :

- $solve(L, mid-1)$
- $solve(mid+1, R)$


**Kemungkinan 2 : Gak ada benteng di posisi yang kita tembak**

Let's say sekarang kita rekursi ke $solve(6, 10)$ dan kita ambil titik tengah di $8$, berarti kita ambil tembakan ke $(8, 8)$


Nah disini kita bisa liat query kita ngembaliin nilai $d > 0$. Dalam kasus ini, kita bisa "menyimpan" nilai mid sementara ini sebagai titik $P$

Jadiii definisinya, titik $P$ ini adalah **suatu titik dimana titik ini gak dilewatin benteng sama sekali**

Secara formal, $(P, P)$ adalah titik yang gak dilewatin benteng (artinya ngga ada benteng yang memiliki $x = P$ atau $y = P$)

Titik inilah titik **KUNCI** buat menyelesaikan full solution di problem ini dan titik ini bisa merupakan titik apapun yang gak dilewatin benteng (misal dalam kasus kita ini, $P = 8$)

---

**Full Solution**

Dari dua observasi diatas, udah cukup buat dapet full solution :wink:

NANI!??

Oke jadi sejauh ini kita bisa summarize yang bisa kita dapetin dengan menjalankan ide di observasi 2 :

- Sebuah himpunan $Q$ yang berisi $q_1, q_2, ..., q_{|Q|}$ yaitu titik titik yang **mungkin** ada bentengnya
- Sebuah titik $P$ yang terletak di koordinat $(P, P)$ dimana titik ini gak dilewatin benteng

Kalo dalam ilustrasi kita :


Nah tapi masalahnya, gimana caranya kita tau si $q_i$ itu termasuk di garis yang vertikal atau horizontal?

**NAH disinilah observasi game changer dari titik $P$**

Kita bisa nanya pake strategi gini :

- $ask(q_i, P) = 0$, maka sudah **pasti** ada benteng di $x = q_i$. Kenapa? karena tadi kita tau di titik $(P, P)$ gak ada bentengnya, artinya bentengnya cuma mungkin ada di $x = q_i$
- $ask(P, q_i) = 0$, maka sudah **pasti** ada benteng di $y = q_i$ (dengan logika yang sama)

Jadi disini kita tinggal tanya pertanyaan tambahan sebanyak $2(N+M)$


Jadi dari jawaban yang didapatkan diatas kita bisa simpulin kalo benteng yang ada di $x$ terletak di sumbu $x = \{2, 5, 8\}$ dan benteng yang terletak di sumbu $y = \{2, 3, 7\}$

---

<center>
<h4>
END
</h4>
</center>