# KSNP Friendly Contest Editorial

## Penulis Soal

| Judul Soal | Author | Editorialist |
| ---------- | ------ | ----------- |
| A. Gura dan Social Distancing | TunaSandwich | TunaSandwich |
| B. Membantu Matsuri Memilih Murid | MGS763 | MGS763 |
| C. Liburan Miko | ainunsy1 | tzaph, JvThunder |
| D. Sora dan Perjalanan Waktu | tzaph | tzaph |
| E. Kereta Api Suisei | CyberSleeper | CyberSleeper |
| F. Hacker Pekora |JvThunder |JvThunder |
| G. Aqua dan Perjalanan Waktu |joshjms |joshjms |

## A. Gura dan Social Distancing

Sediakan array of boolean ``visited`` bernilai false yang berfungsi untuk mengecek ``grid[i][j]`` sudah dikunjungi atau belum. Iterasikan keseluruhan grid, jika ``grid[i][j] == '1'`` berikan nilai true pada ``visited[i][j]`` dan cek sekelilingnya juga (atas, bawah, kanan, kiri, atas-kiri, atas-kanan, bawah-kiri, bawah-kanan) atau bisa juga dituliskan sebagai cek grid : $(i-1, j); (i+1, j); (i, j+1); (i, j-1); (i-1, j-1); (i-1, j+1); (i+1, j-1); (i+1, j+1)$ sama dengan '1' atau tidak. Jika iya, tambahkan pada variabel yang menyimpan nilai banyaknya udang yang harus dihukum. Selama mengecek tetangga dari ``grid[i][j]``, pastikan bahwa tetangga dari $(i,j)$ ada di dalam area pos.

Untuk mengeluarkan koordinat dari pos-pos udang yang harus dihukum, iterasikan keseluruhan array ``visited``. Jika ``visited[i][j]`` bernilai true, keluarkan ``i`` dan ``j``.

#### Kompleksitas: $O(N^{2})$

Link solusi:
(C++, TunaSandwich) https://ideone.com/kuOxe9
(Python 3, tzaph) https://ideone.com/m5XFDt

## B. Membantu Matsuri Memilih Murid

Definisikan cost suatu kelompok sebagai nilai kecemburuannya.

Pertama-tama, kita urutkan dulu barisan $A$ secara menaik. Perlu diperhatikan bahwa apabila $A_i$ dan $A_j$ berada di kelompok yang sama untuk suatu $i<=j$, maka apabila suatu $A_k$ $(i<k<j)$ juga masuk ke dalam kelompok tersebut, cost kelompok tersebut tidak akan bertambah, sehingga untuk menghemat cost suatu kelompok, kita hanya perlu memilih suatu range $[l,r]$ dan memasukkan setiap $A_i$ $(l \le i \le r)$ ke dalam kelompok tersebut. Cost dari kelompok tersebut adalah $A_r - A_l$.

Jika kita memilih $[l_i,l_{i+1}-1]$ sebagai range kelompok ke-$i$ untuk setiap $1 \le i \le k$ ( $l_1=1$ , $l_{k+1}=n+1$ , dan $l_i<l_{i+1}$), maka total cost yang didapatkan adalah $sum = \sum_{i=1}^{i=k}({A_{l_{i+1}-1}}-{A_{l_i}})$. Padahal, $sum + \sum_{i=2}^{i=k}(A_{l_i} - A_{l_i-1}) = A_n - A_1$, sehingga untuk meminimalkan total cost, kita hanya perlu memilik $k-1$ index $i$ $(1 \le i \le n-1)$ dengan $(A_{i+1}-A_i)$ terbesar, lalu mengurangkannya dari $A_n - A_1$.

#### Kompleksitas: $O(N log N)$

Link Solusi:
(C++, MGS763) https://ideone.com/XO332r
(Python 3, tzaph) https://ideone.com/5tvf23

## C. Liburan Miko

Jawaban dari soal ini adalah $N!$

### Proof
Misalkan $F(N)$ adalah banyaknya konfigurasi pohon biner untuk $N$. Akan dibuktikan dengan induksi bahwa $F(N) = N!$.

Jelas bahwa $F(0)=1$.
Misalkan $F(N) = N!$ benar untuk semua $F(i)$ dengan $0 \le i < N$.

Jelas bahwa angka pada root dari pohon biner ini adalah $N$. Lalu, anak kirinya merupakan pohon dengan ukuran $X$, sedangkan anak kanannya merupakan pohon dengan ukuran $N-X-1$.

Banyaknya cara untuk memilih $X$ angka untuk pohon di sebelah kiri ada $\binom{N-1}{X}$, dan banyaknya cara konfigurasi anak sebelah kiri itu $F(X)$, sedangkan anak sebelah kanannya $F(N-X-1)$.

Jadi soalnya sama dengan $\sum_{X = 0}^{N - 1} \binom{N-1}{X} \times F(X) \times F(N - 1 - X)$.

Dari klaim sebelumnya, kita bisa simpulkan bahwa $\binom{N-1}{X} \times F(X) \times F(N-X-1) = \binom{N-1}{X} \times X! \times (N-X-1)! = (N-1)!$

Maka, $F(N) = \sum_{X = 0}^{N - 1} (N - 1)! = N!$ <b>Terbukti.</b>

### Proof 2
Kita dapat menghitung jumlah konfigurasi dengan mengkonstruksi pohon biner mulai dari root, kemudian menambahkan anak-anaknya. Perhatikan bahwa suatu parent harus lebih besar dari seluruh elemen di subtree parent tersebut. Maka, $N$ akan selalu menjadi root dari pohon biner. Anggap kita mempunyai pohon biner dengan 1 node $N$. Setelah itu, kita akan menambahkan angka kebawah tree tersebut dalam urutan $N-1,N-2,...,1$, karena jika ingin menambahkan node $x$, parent dari $x$ harus lebih besar dari $x$. Sekarang, kita akan menghitung banyaknya konfigurasi dengan cara ini. Untuk angka pertama yang dimasukkan, akan ada $2$ slot, yaitu anak kiri dan anak kanan dari root. Lalu, menambahkan suatu node $x$, slot akan selalu bertambah $1$, karena slot yang ditempati node $x$ tidak dapat dipakai, mengurangi $1$ slot lama, namun anak kiri dan anak kanan dari node $x$ menambahkan $2$ slot baru. Berarti ketika menambahkan $N-2$ akan ada $3$ slot yang dapat ditempati, dan seterusnya sampai terdapat $N$ slot ketika menambahkan $1$. Maka, terdapat $2 \times 3 ... \times N = N!$ pohon biner.

#### Kompleksitas: $O(N)$

Link Solusi:
(C++, ainunsy1) https://ideone.com/xzNFxd
(Python 3, tzaph) https://ideone.com/fhn1tG

## D. Sora dan Perjalanan Waktu

### Subsoal 1

Subsoal ini hanya bekerja sebagai bait untuk mencoba menvisualisasikan cara kerja soal. Mungkin saja ada solusi $O(N!)$ atau solusi dynamic programming bitmask $O(N^2 \times 2^N)$. Details left for the reader.

### Subsoal 2

Subsoal ini bekerja sebagai indikasi bahwa solusi anda sudah benar, tetapi terdapat bug yang membuat solusi anda Time Limit Exceeded pada subsoal terakhir.

### Subsoal 3

Jawaban dari soal ini adalah [Minimum Spanning Tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) dari graph tersebut. Cara mencari MST dari suatu graph bisa dicari di google. Untuk KSN, disarankan untuk mempelajari algoritma Kruskal atau algoritma Prim.

Editorial di bawah bertujuan untuk membuktikan kenapa jawaban untuk soal ini adalah MST dari graph.

Pertama, perhatikan bahwa rute Sora harus membentuk sebuah *connected graph*, karena jika terdapat suatu kota yang belum pernah dikunjungi sebelum, Sora tidak bisa menggunakan mesin waktu dan harus melewati sebuah jalan menuju kota tersebut. Jika tidak mungkin terdapat sebuah *connected graph* (dalam kata lain, graph tersebut *disconnected*), maka tidak ada rute untuk Sora, dan jawaban untuk kasus ini adalah $-1$.

Kita tahu bahwa sebuah *Minimum Spanning Tree* dari sebuah graph merupakan jumlah weight minimum dari semua subgraph yang melewati semua $N$ titik pada graph. Maka, jika kita membuktikan bahwa Sora bisa menggunakan rute MST, maka jawaban ini adalah jawaban minimum.

Misalkan minimum spanning tree terlihat seperti gambar kiri di bawah ini. Kita bisa mengambil sembarang *path* dari $1$ ke sebuah kota lain. *Path* tersebut akan kita buatkan sebagai patokan untuk perjalanan Sora.


[Maaf kalau gambar kurang jelas :)]

Pada saat kita memulai dari kota $1$, kita mengunjungi dahulu semua kota yang bisa dikunjungi dari kota $1$ dan tidak melewati *path* patokan. Dalam kata lain, kita akan mengunjungi kota-kota yang dilingkari oranye dan kuning.

Jika Sora berhasil mengunjungi kota-kota yang dilingkari oranye, ia bisa melakukan perjalanan waktu menuju kota 1, lalu ia melanjutkan perjalanannya ke kota-kota yang dilingkari warna kuning. Jika ia sudah selesai, ia melakukan perjalanan waktu menuju kota 1. Ini dilakukan seterusnya sehingga semua kota yang dapat dikunjungi dari kota $1$ dan tidak melewati *path* patokan sudah dikunjungi semua.

Sora akan menuju ke kota selanjutnya pada *path* patokan tersebut (di sini, ia menuju kota $2$). Sora dapat melakukan hal yang sama seperti kota $1$ tadi. Proses ini diulang sehingga ia sampai di ujung *path* patokan. Dengan ini, semua kota terkunjungi dan menggunakan waktu yang minimum pula. <b>Terbukti</b>.

#### Kompleksitas: $O(MlogM)$ atau $O(MlogN)$, tergantung algoritma MST yang digunakan.

Link solusi:

Prim's algorithm (C++, CyberSleeper): https://ideone.com/qEKluv
Kruskal's algorithm (C++, tzaph): https://ideone.com/BCP0Li
Kruskal's algorithm (Python 3, tzaph): https://ideone.com/631qh9

## E. Kereta Api Suisei

### Subsoal 1

**Definisi.** $path(i, j)$ sebagai waktu minimum yang diperlukan untuk pergi dari stasiun $i$ ke stasiun $j$.

Kita misalkan stasiun sebagai *node* dan rel sebagai *edge* dari suatu *graph*. Terdapat $N$ *nodes* dan $N-1$ *edges*. Maka *graph* yang diberikan pasti merupakan *tree*. Asumsikan stasiun pusat sebagai *root* dan stasiun ujung sebagai *leaf*.

Karena setiap gerbong kereta selalu pergi menuju stasiun yang lebih dekat dengan *root*. Maka, gerbong kereta yang dihasilkan oleh stasiun $i$ yang merupakan *leaf* akan sampai di *root* pada detik ke-$(path(i, 1)+1)$ sampai detik ke-$(path(i, 1)+K_i)$.

Perhatikan bahwa gerbong kereta yang bertabrakan hanya menyisakan $1$ gerbong kereta, bukan menghancurkan seluruhnya. Sehingga, hanya ada $0$ atau $1$ kereta yang bisa sampai di stasiun pusat pada setiap detiknya. Kita bisa membuat sebuah *array boolean* yang bernilai $1$ jika ada gerbong kereta yang datang pada detik tersebut, dan $0$ jika tidak.

#### Kompleksitas: $O(\sum K)$

### Subsoal 2

Kita bisa melihat gerbong kereta di setiap leaf sebagai suatu segmen yang dimulai di $(path(i, 1)+1)$ dan diakhiri di $(path(i, 1)+K_i)$. Sehingga kita bisa menggunakan [Sweep Line Algorithm](https://en.wikipedia.org/wiki/Sweep_line_algorithm) untuk menyelesaikan soal ini.

#### Kompleksitas: $O(NlogN)$

Link solusi:
Subsoal 1 (C++, CyberSleeper): https://ideone.com/U1Q3SZ
Subsoal 2 (C++, CyberSleeper): https://ideone.com/Gq5gsY
Subsoal 2 (Python 3, tzaph, credits to Pa.Nic): https://ideone.com/I7T5dV

## F. Hacker Pekora

### Solusi 1

Pertama, lakukan binary search menggunakan pertanyaan tipe $1$ untuk mengetahui nilai dari $A_i+B_i \bmod N$ untuk setiap $0 \leq i < N$ dalam $N \log N$ pertanyaan. Setelah itu, kita cari suatu index j sehingga $A_j$ = $B_0$ menggunakan pertanyaan tipe $2$ dalam $N$ pertanyaan. Lalu, karena properti khusus dari barisan A, yaitu $A_i+1 \equiv A_{i+1} \bmod N$, kita dapat menyimpulkan bahwa, $A_0+j \equiv A_j \bmod N$.

Maka menggunakan informasi bahwa $A_0+j = B_0$ dan $A_0+B_0 \bmod N = k$ dimana $k$ adalah hasil dari binary search sebelumnya, dapat disimpulkan bahwa $2 \cdot A_0 \equiv k-j \bmod N$. Karena $N$ ganjil, maka kita selalu dapat mencari sebuah bilangan $inv$, dimana $inv \cdot 2 \equiv 1 \bmod N$ dengan mengalikan $inv$ di kedua ruas pada persamaan $2 \cdot A_0 \equiv k-j \bmod N$, didapat bahwa $A_0 = inv \cdot (k-j) \bmod N$. Dengan itu, kita dapat mengetahui nilai dari $A_i$ untuk setiap $0 \leq i < N$. Lalu, kita dapat menggunakan nilai dari $A_i+B_i \bmod N$ untuk mengetahui nilai dari $B_i$,

Total pertanyaan yang diperlukan adalah $(N \log N + N)$ pertanyaan.

#### Kompleksitas: $O(N log N)$

Link solusi: https://pastebin.com/upZjyUXE

---

### Solusi 2 (tzaph)

Sama dengan solusi 1, kita akan mencari $A_i + B_i \pmod N$ untuk setiap $0 \le i < N$ menggunakan *binary search* dan menggunakan $NlogN$ pertanyaan tipe $1$.

Perhatikan bahwa terdapat $N$ kemungkinan permutasi untuk $A$, yaitu semua kemungkinan rotasi $\{0, 1, \dots, N - 1\}$. Jika diketahui $A_i + B_i \pmod N$, hanya terdapat satu permutasi $B$ yang mungkin untuk setiap $A$.

Untuk memvisualisasikan, misalkan $N = 5$ dan $A + B \pmod N = \{1, 3, 1, 3, 2\}$.

Terdapat $5$ kemungkinan pasangan $A$ dan $B$:

- $a_0 = \{0, 1, 2, 3, 4\}$ dan $b_0 = \{1, 2, 4, 0, 3\}$
- $a_1 = \{4, 0, 1, 2, 3\}$ dan $b_1 = \{2, 3, 0, 1, 4\}$
- $a_2 = \{3, 4, 0, 1, 2\}$ dan $b_2 = \{3, 4, 1, 2, 0\}$
- $a_3 = \{2, 3, 4, 0, 1\}$ dan $b_3 = \{4, 0, 2, 3, 1\}$
- $a_4 = \{1, 2, 3, 4, 0\}$ dan $b_4 = \{0, 1, 3, 4, 2\}$

Perhatikan bahwa pasangan-pasangan tersebut dinomori sehingga $a_{i, i} = 0$ dan $b_{i, j} + 1 \equiv b_{i + 1 \pmod N, j} \pmod N$ untuk semua $0 \le i < N$. Perhatikan pula bahwa $a_{x, y} = y - x \pmod N$.

Terdapat juga $5$ pasangan berbeda $(u, v)$ sehingga $a_{i, u} = b_{i, v} = 0$, yaitu:

- $(0, 3):$ $a_{0, 0} = b_{0, 3}$
- $(1, 2):$ $a_{1, 1} = b_{1, 2}$
- $(2, 4):$ $a_{2, 2} = b_{2, 4}$
- $(3, 1):$ $a_{3, 3} = b_{3, 1}$
- $(4, 0):$ $a_{4, 4} = b_{4, 0}$

Karena $A$ dan $B$ merupakan salah satu dari $5$ kemungkinan pasangan tersebut ($A = a_i$ dan $B = b_i$ untuk suatu 0 \le i < N$), hanya satu $(u, v)$ dari pasangan di atas yang memenuhi $A_u = B_v = 0$.

Menariknya, hanya pasangan ini juga yang memenuhi $A_u = B_v$, dan lainnya tidak akan memenuhi. Maka, kita bisa melakukan pertanyaan tipe kedua $N$ kali sesuai dengan pasangan di atas, dan hanya satu pertanyaan yang akan dijawab `Y`. Kita bisa *backtrack* dan mendapatkan konfigurasi permutasi dari pasangan yang benar itu.

---

#### Proof

Andaikan terdapat lebih dari satu pasangan yang memenuhi. Misalkan kedua pasangan tersebut adalah $A_i = B_j$ dan $A_k = B_l$ dengan $i \ne k$. WLOG, $A_i = 0$. Dari sini, kita tahu bahwa $A = a_i$, $B = b_i$, dan $a_{i, i} = b_{i, j} = 0$. Kita juga tahu bahwa $a_{k, k} = b_{k, l} = 0$.

Dari $a_k$ dan $b_k$, kita dapat bahwa
$$A_l + B_l \equiv a_{k, l} + b_{k, l} = a_{k, l} \equiv l - k \pmod N$$

Karena $A_i = 0$, maka $A_k = B_l \equiv k - i \pmod N$ dan $A_l \equiv l - i \pmod N$. Maka,
$$A_l + B_l \equiv (l - i) + (k - i) = l + k - 2i \pmod N$$

Menggabungkan kedua informasi di atas, kita punya,

$$l - k \equiv l + k - 2i \pmod N$$

$$2k \equiv 2i \pmod N$$

Karena kita mempunyai $0 \le i, k < N$ dan $N$ merupakan angka ganjil, $i = k$. Ini berkontradiksi dengan asumsi kita di awal bukti ini.

<b>Terbukti.</b>

----

Total pertanyaan yang diperlukan adalah $(N \log N + N)$ pertanyaan. Kompleksitas waktu adalah $O(N^2)$ atau $O(N)$ tergantung implementasi.

Link Solusi:
$O(N^2):$ https://ideone.com/aJ56PP (C++)
$O(N):$ https://ideone.com/ELa0VX (C++)
$O(N):$ https://ideone.com/Uy9iqJ (Python 3)

## G. Aqua dan Perjalanan Waktu

### Subsoal 1

Pertama, kita selesaikan dulu subsoal 1 dimana array $A$ terurut menaik. Nyatakan uang yang kita dapatkan setelah perjalanan waktu melalui segmen $[l..r]$ sebagai $m_{l, r}$. Bisa diperhatikan bahwa formula $m_{l, r} = \sum_{i=l}^{r} C_i - (A_r - A_l)$. Kita dapat menggunakan prefix sum untuk mendapatkan $\sum_{i=l}^{r} C_i$. Sekarang kita dapat $m_{l, r} = pref[r] - pref[l - 1] - (A_r - A_l) = pref[r] - A_r + A_l - pref[l - 1]$. Kita dapat memilih segmen $[l, r]$ dengan mengiterasikan semua kemungkinan $r$ dalam $O(N)$ dan memilih $l$ yang memiliki $A_l - pref[l - 1]$ maksimum. Untuk mengurus kasus dimana $abs(A_r - A_l) > k$, kita dapat menggunakan max-heap untuk menyimpan tiap nilai $A_l - pref[l - 1]$ dan membuangnya (pop) bila diperlukan.

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

---

### Subsoal 2

Setelah menyelesaikan subsoal 1, dapat diperhatikan bahwa subsoal 2 menggunakan ide yang sama. Metode prefix sum tetap dapat kita gunakan untuk mendapatkan $\sum_{i=l}^{r} C_i$. Untuk $A$, kita simpan index tiap elemen $A$ dan sort secara terurut menaik. Dari sini, soal akan berupa sangat mirip dengan subsoal 1. Akan tetapi terdapat beberapa perbedaan: Setelah di sort, sebuah index $i$ dapat menjadi $l$ bila $A_r < A_i$ atau menjadi $r$ bila $A_i > A_l$. Jika $i$ adalah $l$, maka $m_{i, r} = pref[r] - A_r + A_i - pref[i - 1]$, dan jika $i$ adalah $r$, maka $m_{l, i} = pref[i] - A_i + A_l - pref[l - 1]$. Di max-heap pertama kita anggap $i$ adalah $l$ dengan menyimpan $pref[r] - A_r$ sedangkan di max-heap kedua kita anggap $i$ adalah $r$ dengan menyimpan $A_l - pref[l - 1]$.

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

---

Link Solusi

(Solusi #1 - joshjms C++)
https://ideone.com/T2J6FL

(Solusi #2 - JvThunder C++)
https://ideone.com/AhCXoy