# Editorial Simulasi OSN 2022 - 2A
## by kokocoder (unofficial)

---

<center><h3>Soal 2A</h3></center>


**Observasi 1**
(dapet dari subtask yang $N$ sama $K$ nya kecil ~~kayak peluang dia naksir sama kamu~~)

Disini kita bisa pake DP. Statenya simpen apa aja? Posisi kita sekarang di kota mana, sama kita udah ngunjungin berapa kota

Sebut aja definisi dari $dp(i, j)$ adalah :
**Banyak nanas maksimal yang bisa kita dapat kalau kita mau pergi dari kota ke $i$ ke kota akhir perjalanan kita dan saat ini kita udah ngambil $j$ langkah**

Atau gampangnya kalo misalnya rute perjalanan kita adalah :

$1$ -> $u_1$ -> $u_2$ -> ... -> $i$ -> ... -> $u_K$

maka $i$ adalah kota yang kita kunjungi di urutan ke $j$ ($u_j$)

Dari sini kita bisa dapat transisi dari $dp(i, j)$ yaitu :

$dp(i, j) = max(dp(v_1, j+1) + B_i, dp(v_2, j+1) + B_i, ..., dp(v_K, j+1) + B_i)$
$dp(i, j) = max(dp(v_1, j+1), dp(v_2, j+1), ..., dp(v_K, j+1)) + B_i$

(pindah dari kota ke $i$ ke kota lain yang biaya pindahnya masih masuk budget, terus cari yang menghasilkan poin paling tinggi, kemudian ditambah $B_i$)

dimana $v_x$ adalah himpunan kota-kota yang bisa dikunjungi dari kota ke $i$ yang biaya pindahnya itu berada di dalam batasan budget yang kita punya

Secara formal, $v_x$ adalah himpunan bilangan bulat dimana $L_j ≤ A_{i, v_x} ≤ R_j$

Contohnya kita punya matrix $A$ yang isinya kayak gini deh

Let's say sekarang kita berada di kota $4$ dan punya budget travelling diantara $[3 .. 8]$ ($L_j = 3$ dan $R_j = 8$)

Berarti kota kota yang bisa kunjungi dari kota $4$ adalah kota $2$ dan $3$ karena biaya untuk pindah dari $4$->$2$ = $5$ dan dari $4$->$3$ = $6$

Maka :
$dp(4, j) = max(dp(2, j+1), dp(3, j+1)) + B_4$

Dengan gini, kompleksitas DP kita jadi $O(N^2K)$ (karena $O(NK)$ buat state DP nya, dan $O(N)$ sisanya buat transisi pindah dari suatu kota ke kota lain)

---

**Observasi 2**
(dapet dari subtask yang $L_i = 1$ dan $R_i = 10^9$) yang artinya dari suatu kota kita bisa pindah ke kota manapun)

Oke jadi kalo kita liat yang bikin DP kita itu lambat ~~kayak kecepatan dia ngebalas chat kamu~~, itu karena ada transisi $O(N)$ nya dari suatu kota ke kota lain. Sekarang kita bisa liat suatu fakta menarik

Misalnya saat ini kita lagi mau ngisi $dp(i, j)$ buat suatu state. Nah di table DP nya, sama aja kayak gini :


Nah karena kita bebas pergi dari kota $i$ ke kota manapun, jadi dari rumus DP yang kita dapat diatas, kita tahu bahwa :

$dp(i, j) = max(dp(1, j+1), dp(2, j+1), ..., dp(N, j+1)) + B_i$

atau kalo kita liat di tabel nya :


Nah gimana cara kita cari nilai maksimal dari $dp$ ini? Kita bisa pake ......

**SEGMENT TREE**
(nah lhooo....)

Karena kan kita mau query nilai maksimal dari range $[1..N]$, berarti kita tinggal bikin segment tree dimana node nya nyimpan informasi $dp$ dengan nilai maksimum di baris berikutnya didalam segmennya.

Nah baru nanti setiap kali kita selesai ngisi 1 baris, segment tree nya di update buat setiap indeks supaya bisa dipake buat ngisi $dp$ di baris sebelumnya lagi

:exploding_head:

Dengan gini, kompleksitas $dp$ kita ke reduce dari $O(N^2K)$ jadi $O(NK log N)$

---

**Observasi 3**
(sekaligus full solution)

Nah observasi yang kita pake di 2 observasi sebelomnya bakal dipake disini

Bedanya, sekarang dari kota ke $i$ kita gak bisa pergi dari kota sembarang dan kita cuma bisa pergi ke kota kota yang masuk budget. Caranya gimana?

Nahh... disini ada **observasi kunci** yang ada di constraintnya

Di bagian constraint kita bisa liat bahwa :
**Untuk setiap $1 ≤ j < k ≤ N$ berlaku :
$1 ≤ A_{i, j} < A_{i, k} ≤ 10^9$**

Artinya disini, dalam satu baris kan berarti cost nya pasti *monotonic increasing*

Misal kalo kita liat di matrix $A$ kita yang tadi :

dan budget kita adalah $[3 .. 8]$ ($L_j = 3$ dan $R_j = 8$), berarti kota kota yang memenuhi syarat adalah kota $2$ dan $3$, yang artinya di $dp$ kita nanti, transisinya bakal :

$dp(4, j) = max(dp(2, j+1), dp(3, j+1)) + B_4$


Jadi kita tinggal ngelakuin range maximum query dari $[2..3]$

Nah batasan dari range ini bisa kita cari pake *binser* (binary search) ajaa

Cuma kita mesti ati-ati karena disitu ada keterangan kalo $A_{i, i} = 0$, jadi buat mempermudah implementasi, kalian bisa bikin array of vector aja yang isinya tidak mengandung si angka $0$ ini, supaya nanti buat binser batas atas sama bawahnya bisa kita cari dari vector itu

Jadi kompleksitasnya tetap $O(NK log N)$ (buat binser + RMQ)

---

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