# Programming and Logic Competition Editorial
## Penulis Soal

| Judul Soal | Penulis | Editorialis |
|:----------:| ------- | ----------- |
|A. Kembar | Nabil Ervatra | Nabil Ervatra |
|B. Longest Increasing Substring | Rico Filberto | Rico Filberto |
|C. Menyeberangi Danau [REMOVED] | Maximilliano Utomo | Maximilliano Utomo |
|D Robot Mainan | Steven Novaryo | Steven Novaryo |
|E. Menghapus Palindrom | Maximilliano Utomo | Maximilliano Utomo |
|F Bubble Sort | Steven Novaryo | Steven Novaryo |
|G. Kelinci Bulan | Maximilliano Utomo | Maximilliano Utomo |
|H. Lambung Cembung | Maximilliano Utomo | Maximilliano Utomo |
|I. Nabil dan Ikan | Nabil Ervatra | Nabil Ervatra |

---
## A
Keluarkan $1$ apabila banyaknya permen ganjil, keluarkan $0$ apabila genap.

Kompleksitas waktu: $O(1)$.
Kode : https://ideone.com/1ggrFm

---
## B

Kita bisa menyelesaikan soal ini dengan menggunakan *dynamic programming*.

Misalkan $f(pos,len)$ menyatakan banyaknya *substring* maksimum yang dapat dibentuk apabila *substring* yang terakhir kali dibentuk adalah $S[pos...pos+len-1]$.

Selanjutnya misalkan $nextLen$ merupakan panjang minimum dari suatu *substring* sehingga dapat memenuhi persyaratan $S[pos+len...pos+len+nextLen-1] > S[pos...pos+len-1]$. Perhatikan, sebenarnya hanya terdapat 2 nilai yang dapat memenuhi nilai $nextLen$, yaitu:

- $nextLen = len$, nilai $nextLen$ setidaknya harus sama dengan $len$ sehingga persyaratan tersebut dapat dipenuhi, karena pada soal ini dapat dijamin setiap *substring* yang dapat dibentuk tidak akan memiliki *leading zero*. Namun kita tetap perlu mengecek apakah $S[pos+len...pos+2*len-1] > S[pos...pos+len-1]$, untuk menunjukkan apakah $nextLen = len$.
- Namun apabila $S[pos+len...pos+2*len-1] \leq S[pos...pos+len-1]$, maka dapat dijamin $nextLen = len+1$. (Hal ini bisa ditunjukkan dengan ide: kita bisa langsung mengetahui angka dengan 10 digit pasti lebih besar dibandingkan angka dengan 9 digit, apabila digit pertama dari kedua angka tersebut bukanlah nol)

Sehingga kita bisa mendapatkan transisi dari fungsi DP kita yaitu:
$$f(pos,len)=max(f(pos,len+1), f(pos+len,nextLen) + 1)$$

- Mengapa transisi $f(pos,len+1)$ dibutuhkan? Hal ini disebabkan, pengambilan *substring* selanjutnya dengan panjang $nextLen$ bisa saja tidak optimal, sehingga kita juga perlu mencoba pengambilan *substring* selanjutnya dengan panjang $nextLen+1, nextLen+2,...,dst$.
(Contoh kasus: $''9119189211212213214''$, seharusnya bisa dipecah menjadi: $9,119,189,211,212,213,214$)

Maka kompleksitas memori dari DP tersebut: $O(|S|^2)$

Kita bisa melakukan *pruning* pada DP yang kita buat. Perhatikan bahwa sebenarnya kasus terburuk (kasus yang membentuk jawaban terkecil) terjadi saat semua angka pada *string* memiliki nilai yang sama. Sehingga cara paling optimal untuk memecahnya adalah dengan panjang $1,2,3,4,...,\sqrt{2|S|}-1,\sqrt{2|S|}$. ($\sqrt{2|S|}$ perkiraan yang bisa didapatkan dengan menggunakan rumus deret aritmatika).

Dari kasus terburuk tersebut kita dapat membuat argumen apabila $len$ dari *substring* yang kita bentuk melebihi nilai $\sqrt{2|S|}$ maka kita sudah tidak perlu mencari lagi nilai dari $f(pos,len)$, karena kita bisa menyatakan bahwa hasil dari fungsi tersebut pasti akan lebih kecil dibandingkan jawaban yang dihasilkan pada kasus terburuk. (Ide ini bisa didapatkan dengan pernyataan: semakin panjang *substring* yang kita bentuk maka jumlah *substring* dapat kita bentuk akan semakin sedikit)

Dari *pruning* tersebut maka kompleksitas memori dari DP menjadi: $O(|S|\sqrt{2|S|})$

Namun masih terdapat permasalahan yang belum diselesaikan, yaitu bagaimana cara menentukan nilai $nextLen$ dengan cepat.

Cara sederhana untuk menentukan nilai $nextLen$ adalah dengan melakukan iterasi $O(len)$ untuk membandingkan masing-masing karakter pada *substring* $S[pos+len...pos+2*len-1]$ dengan $S[pos...pos+len-1]$. Terdapat 3 kasus pada saat membandingkan karakter pada saat iterasi ke-$i$, yaitu:

- $S[pos+i]=S[pos+len+i]$, maka lanjutkan iterasi.
- $S[pos+i]<S[pos+len+i]$, maka $nextLen = len$ dan iterasi dapat dihentikan.
- $S[pos+i]>S[pos+len+i]$, maka $nextLen = len+1$ dan iterasi dapat dihentikan.

Apabila hingga akhir iterasi nilai setiap karakter sama, hal ini menandakan $S[pos+len...pos+2*len-1] = S[pos...pos+len-1]$ yang berarti $nextLen = len+1$.

Tetapi dengan cara tersebut maka kompleksitas waktu dari DP adalah: $O(|S|(\sqrt{2|S|})^2)=O(|S|^2)$

Sekarang perhatikan bahwa saat melakukan pembandingan, kita bisa langsung menghentikan pembandingan saat pertama kali kita menemukan $S[pos+i]!=S[pos+len+i]$. Sehingga sekarang kita ingin mencari cara agar dapat menemukan posisi $i$ dengan cepat.

Terdapat beberapa algoritma bisa digunakan untuk menyelesaikan permasalahan tersebut, yaitu;

- *Extended KMP* atau *suffix array* (2 algoritma yang berbeda, cukup pakai salah satu saja). Dengan melakukan prekomputasi pada *string* $S$ kita dapat mencari posisi $i$ dalam kompleksitas waktu $O(1)$.
(Apabila menggunakan *extended KMP*, maka kita dapat membentuk *extended KMP* untuk setiap index pada *string* $S$, namun untuk setiap index kita hanya perlu membentuknya hingga panjang $2\sqrt{2|S|}$)
(Apabila menggunakan *suffix array*, maka untuk mencari posisi $i$ dapat menggunakan *LCP (Lowest Common Prefix)*)

Sehingga kompleksitas waktu: $O(|S|\sqrt{2|S|})$.

- *Hashing + binary search*, kita dapat membuat *rolling hash* dari string $S$, kemudian kita dapat melakukan *binary search* untuk mencari posisi $i$, dengan cara membandingkan nilai hash dari kedua *substring* yaitu dengan cara: Jika, $hash(S[pos...pos+mid])=hash(S[pos+len...pos+len+mid])$, maka posisi $i>mid$, namun jika tidak sama menandakan posisi $i\leq mid$. Maka dengan menggunakan *binary search* kita dapat menentukan posisi $i$ dalam kompleksitas waktu: $O(\log(len))$ atau $O(\log(\sqrt{2|S|}))$

Sehingga kompleksitas waktu: $O(|S|\log(\sqrt{2|S|})\sqrt{2|S|})$
Apabila dihitung sebenarnya solusi *hashing + binary search* seharusnya terkena *Time Limit Exceeded*, namun dengan membuat program yang memiliki efsiensi yang tinggi, atau melakukan beberapa *pruning* lainnya. Maka solusi ini juga bisa mendapatkan *Accepted*.

Catatan: Masih ada beberapa solusi lain yang dapat menghindari penggunaan algoritma *string* (3 algoritma yang dibahas diatas bisa dikategorikan sebagai algoritma *string*).

Kode *extended KMP* : https://ideone.com/4H0Zjf
Kode *hashing + binary search* : https://ideone.com/LdNw84
Kode *suffix array* : https://ideone.com/DdLijn

---
## C [REMOVED]

Terdapat counter pada soal ini, yaitu pada saat $A \ge 3$ dimana kita bisa mensimulasikan *tower of hanoi* sehingga $N = \infty$.

### Expected solution:

Kita bisa menyelesaikan soal ini dengan *dynamic programming*.

Misalkan $DP[A]$ menyatakan banyaknya tupai maksimum yang bisa menyeberangi danau jika terdapat $A$ batu besar, dengan basecase $DP[0] = B + 1$. Terdapat $B$ batu kecil dimana setiap batu hanya dapat ditempati oleh seekor tupai, dan seekor tupai terakhir dapat menyeberangi ke pulau di tengah danau secara langsung.

Maka, transisi $DP$ tersebut adalah:

$$DP[i] = \sum_{k = 0}^{i - 1}DP[k] + DP[0]$$

- Terdapat $DP[i - 1]$ banyaknya tupai yang bisa menempati batu besar ke-$i$ dengan menggunakan $i - 1$ batu besar pertama.
- Terdapat $DP[i - 2]$ banyaknya tupai yang bisa menempati batu besar ke-$(i - 1)$ dengan menggunakan $i - 2$ batu besar pertama.
- Seterusnya hingga $DP[0]$ tupai menempati batu besar pertama.
- $DP[0]$ tupai akhir bisa menempati pulau di tengah danau. Sisa $\sum_{k = 0}^{i - 1}DP[k]$ mengikuti.

Maka, kita bisa menyimpan jumlah $\sum_{k = 0}^{i - 1}DP[k]$ dan menghitung nilai $DP[A]$. Solusi ini berjalan dalam $O(A)$.

Perhatikan pula bahwa $DP[A]$ dapat direduksi menjadi sebuah *closed formula*:
$DP[A] = \sum_{k = 0}^{A - 1}DP[k] + DP[0]$
$\rightarrow$ $DP[A] = DP[A - 1] + (\sum_{k = 0}^{A - 2}DP[k] + DP[0])$
$\rightarrow$ $DP[A] = DP[A - 1] + DP[A - 1]$
$\rightarrow$ $DP[A] = 2^A \times DP[0]$
$\rightarrow$ $DP[A] = 2^A \times (B + 1)$

Kompleksitas waktu: $O(A)$ atau $O(logA)$.

---
## D

Secara singkat jawabannya adalah <code>YES</code> apabila $N$ genap dan $N \geq 4$ dan <code>NO</code>, jika sebaliknya. Bukti diserahkan kepada pembaca sebagai latihan.
Kompleksitas waktu : $O(1)$
Kode : https://ideone.com/8W1dbL

---
## E

Partisi string tersebut menjadi tiga buah substring:
- Substring pertama berisikan serangkaian 1 atau 0 terpanjang pada posisi awal string.
- Substring kedua adalah *longest alternating substring* tepat setelah substring pertama. Sebuah substring dikatakan *alternating* jika tidak ada karakter bersebelahan yang sama.
- Substring ketiga merupakan sisa string.

Sebagai contoh, $S = 111110101011100100000111010111$ dipartisikan menjadi:
- $11111$
- $010101$
- $1100100000111010111$

Maka jawaban untuk soal ini adalah panjang substring kedua ditambah satu.

Konfigurasi tersebut bisa dicapai sebagai berikut:

Pertama, ubahlah substring pertama menjadi satu karakter saja. Sebagai contoh, $11111$ diubah menjadi $1$.

Kedua, ubahlah substring ketiga menjadi sebuah *alternating string* dengan cara mengubah setiap rangkaian karakter yang sama menjadi satu karakter saja. Sebagai contoh, $1100100000111010111$ diubah menjadi $101010101$.

Ketiga, perhatikan bahwa gabungan dua karakter terakhir dari substring kedua dan dua karakter terawal substring ketiga merupakan sebuah palindrom. Lakukan operasi pada palindrom tersebut dan hapuskan dua karakter terawal dari substring ketiga. Lakukan operasi ini berulang kali sampai semua karakter pada substring ketiga sudah terhapus.

Tidak ada cara lain untuk mendapatkan konfigurasi untuk mendapatkan panjang string yang lebih kecil. Ini bisa dibuktikan dengan intuisi bahwa *alternating substring* pertama tidak mungkin bisa dihapus menggunakan operasi yang diberikan.

Kompleksitas waktu: $O(N)$.
Kode: https://ideone.com/vCnBUa

---
## F

Definisikan $cnt(l, r, i)$ sebagai banyaknya element $i$ pada segment $[l, r]$ dan $inv(l, r)$ sebagai banyaknya <em>inversion</em> dari segment $[l, r]$.
Perhatikan bahwa banyak <em>inversion</em> pada segment $[l, r]$ jika segment $[l, mid]$ dan $[mid + 1, r]$ sudah berurutan adalah $inv(l, r) = cnt(l, mid, 1) \times cnt(mid + 1, r, 0)$. Karena segment $[l, mid]$ dan $[mid + 1, r]$ masing-masing memiliki <em>inversion</em> sebesar $inv(l, mid)$ dan $inv(mid + 1, r)$ untuk diurutkan maka banyak <em>inversion</em> dari segment $[l, r]$ adalah $inv(l, r) = cnt(l, mid, 1) \times cnt(mid + 1, r, 0) + inv(l, mid) + inv(mid + 1, r)$

Oleh karena itu, kita dapat menyelesaikan soal ini menggunakan segment tree.

Kompleksitas waktu: $O((N + Q)logN)$.
Kode : https://ideone.com/LZzVSI

---
## G

Jika kita telah menomori kelinci ke-$i$, maka banyaknya nomor yang tersedia untuk semua kelinci $j$ lainnya dengan $A_j > A_i$ berkurang satu.

Nomori kelinci-kelinci tersebut dari $A_i$ terkecil hingga terbesar. Banyaknya kemungkinan menomori kelinci ke-$i$ adalah $A_i - k$ dimana $k$ merupakan banyaknya kelinci yang sudah dinomori. Jika $A_i - k \le 0$, tidak ada pilihan angka untuk kelinci tersebut, sehingga jawabannya $0$.

Kompleksitas waktu: $O(N)$ atau $O(NlogN)$.
Kode: https://ideone.com/4qPOT4

---
## H

Notasikan $\binom{A}{B}$ sebagai rumus kombinasi, yaitu $\frac{A!}{B!(A-B)!}$.

Banyaknya pasangan bagus sama dengan banyaknya pasangan total dikurangi dengan banyaknya pasangan yang tidak bagus.

Perhatikan bahwa banyaknya titik pada sebuah pasangan himpunan bagus $A$ dan $B$ setidaknya 3 titik agar $CH(A)$ dan $CH(B)$ mempunyai luas positif. Maka, kita tidak perlu menghitung himpunan dengan kurang dari 3 titik.

Banyaknya pasangan total adalah $\sum_{i = 3}^{N - 3}\sum_{j = 3}^{N - j} \binom{N}{i} \times \binom{N - i}{j}$. $\binom{N}{i}$ menyatakan banyaknya cara memilih himpunan titik pertama dan $\binom{N - i}{j}$ menyatakan banyaknya cara memilih himpunan titik kedua.

Sekarang, kita ingin mencari banyaknya pasangan himpunan $A$ dan $B$ sehingga $CH(A)$ dan $CH(B)$ saling lepas.

Kita tetapkan suatu garis yang melewati titik $(X_i, Y_i)$ dan $(X_j, Y_j)$. Misalkan $P$ merupakan himpunan titik $(X_k, Y_k)$ sehingga orientasi $(X_i, Y_i)$, $(X_j, Y_j)$, dan $(X_k, Y_k)$ searah jarum jam. Misalkan $Q$ merupakan himpunan titik $(X_k, Y_k)$ sehingga orientasi $(X_i, Y_i)$, $(X_j, Y_j)$, dan $(X_k, Y_k)$ melawan arah jarum jam.

Jika terdapat himpunan $A$ yang merupakan $(X_i, Y_i)$ dan setidaknya dua titik dari $P$, dan terdapat himpunan $B$ yang merupakan $(X_j, Y_j)$ dan setidaknya dua titik dari $Q$, maka $CH(A)$ dan $CH(B)$ tidak berpotongan dan $(A, B)$ merupakan pasangan himpunan tidak bagus. Banyaknya cara memilih setidaknya dua titik dari $P$ adalah $\sum_{k = 2}^{SIZE(P)} \binom{SIZE(P)}{k}$ dengan $SIZE(P)$ adalah banyaknya titik pada himpunan $P$.

Lakukan ini untuk semua segmen garis $(X_i, Y_i)$ dan $(X_j, Y_j)$ dengan $1 \le i, j \le N, i \ne j$

Kompleksitas waktu: $O(N^3)$
Kode: https://ideone.com/bjaJga

---
## I

Untuk menyelesaikan soal ini kita harus menghitung berapa kali ikan dalam jumlah $i$ $(1 \le i \le K)$ diambil. Kita dapat menghitung $i$ dari $K$ hingga $1$.
Pertama kita akan membagi menjadi beberapa segmen yang setiap segmennya berisi $K$ kotak berurutan kecuali segmen terakhir yang akan berisi $N$ $mod$ $K$ kotak.
Perhatikan bahwa perpindahan ikan paling optimal adalah membagi rata banyaknya ikan ke masing masing segmen. Untuk mengambil $i$ ikan harus terdapat minimal $1$ segmen yang terdapat $i$ ikan di dalamnya.
Kita bisa looping untuk nilai $i$ dari $K$ hingga $1$ dan menghitung berapa kali kita mengambil ikan sebanyak $i$. Kita bisa mengambil ikan sebanyak $i$ sampai jumlah ikan menjadi banyak segmen dikali $(i-1)$. Perhatikan juga segmen terakhir yang terdapat kurang dari $K$ kotak.

Kompleksitas waktu : $O(K)$
Kode : https://ideone.com/uPyNEM