SPOJ DOSA - Lalith Dosa

Soal ini sama sekali tidak ada hubungannya dengan "dosa" dari "berdosa". Jangan tanya saya mengapa judul soalnya seperti itu :)

Soal kali ini tergolong baru ditambahkan di SPOJ dan cukup populer. Terlihat sebagai soal yang mudah, tetapi sebenarnya tidak. Banyak orang yang terjebak dan mendapatkan WA, lalu bertanya-tanya di mana letak kesalahannya kepada sang pembuat soal. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.

Salah satu kasus uji mautnya adalah:

12
10 11 12 10 9 15 16 22 21 19 20 21 

Jawaban seharusnya adalah 4.

Yang harus diperhatikan adalah setiap bilangan pada barisan harus selalu menaik, dan harus berupa bilangan bulat positif.

Seperti biasa, mari kumpulkan observasi-observasi yang mungkin berguna.

Observasi 1:
Mencari banyaknya elemen minimal yang diubah ekivalen dengan mencari banyaknya elemen maksimal yang tidak diubah.

Observasi 2:
Jika persoalan ini ingin barisan bukan harus menaik, tetapi harus tidak boleh turun (diperbolehkan ada bilangan yang sama pada barisan), maka berdasarkan observasi 1, jawabannya adalah N dikurangi LIS (Longest Increasing Subsequence) dari barisan. Hal ini benar karena banyaknya elemen maksimal yang tidak diubah sama saja dengan LIS dari barisan. (Dalam hal ini, LIS dianggap boleh memiliki elemen sama).

Observasi 3:
Untuk menjamin setiap elemen pada barisan akhir merupakan bilangan positif, bisa ditambahkan bilangan dummy bernilai 0 di awal barisan.

Baik, bila soal ini mengizinkan boleh ada elemen yang sama, maka persoalan ini dapat diselesaikan dengan algoritma LIS O(N log N) atau O(N log K). Sayangnya tidak boleh, sehingga kita perlu memodifikasi cara pencarian LIS-nya. Pada kenyataannya, LIS yang kita cari hanya berbeda pada definisi "lebih kecil dari" pada elemen-elemennya.

Misalkan A[i] menyatakan bilangan di posisi ke-i. Maka A[i] dikatakan "lebih kecil dari" A[j] jika dipenuhi:

A[i] + j-i-1 < A[j]

atau bisa dituliskan dalam bentuk lain:

A[i] - i ≤ A[j] - j

Mengapa demikian? Karena di antara posisi ke i sampai ke j diharuskan ada elemen-elemen berbeda yang terus menaik. Seburuk-buruknya, A[i+1] = A[i] + 1, A[i+2] = A[i] + 2, dan seterusnya, atau dengan kata lain A[k] = A[i] + (k-i). Dengan demikian, jika k = j-1, harus dipenuhi A[j-1] = A[i] + (j-i-1) < A[j].

Ternyata, setiap A[i] dapat ditransformasikan menjadi nilai lain secara independen (tidak dipengaruhi dan mempengaruhi elemen lainnya), yaitu menjadi A[i] - i. Oleh karena itu, cukup tranformaskan setiap A[i] menjadi A[i] - 1, lalu cari LIS-nya!

Cara lain untuk memahami transformasinya adalah secara geometris (dan cara ini yang saya gunakan untuk mendapatkan solusinya). Anggap setiap elemen A[i] dinyatakan sebagai titik di koordinat (i, A[i]). Perhatikan gambar berikut:

Pada dua gambar kiri, sesudah A boleh dilanjutkan dengan B karena elemen-elemen di antaranya "bisa diisi" (perhatikan lingkaran kosong pada gambar). Sementara untuk gambar paling kanan, tidak ada cara "mengisi" elemen-elemen di antaranya, sehingga A tidak boleh dilanjutkan dengan B.

Bila setiap elemen dianggap sebagai titik, maka A boleh dilanjutkan ke B jika A ditemui lebih dulu dari B oleh garis y = x + c yang bergerak dengan c mulai dari -∞ sampai ∞ (gerakannya seperti menyapu dari diagonal bawah kanan ke atas kiri). Secara sederhana, titik (x1, y1) akan ditemui garis tersebut lebih dulu dari (x2, y2) apabila dipenuhi y1-x1 < y2-x2. Perhatikan garis putus-putus pada gambar di atas dan Anda akan mengerti maksud saya.

Berikut implementasi saya dengan LIS O(N log N), yaitu dengan bantuan struktur data Binary Indexed Tree max.