Saya akan membahas sebuah persoalan yang menarik, bersumber dari UVa 12384 - Span. Deskripsi soal yang singkat, padat, dan jelas itu mungkin sedikit membingungkan. Pastikan anda mengerti maksud soal atau setidaknya mampu membaca notasi matematikanya. Sebagai informasi, jika A adalah sebuah himpunan, maka |A| menunjukkan banyaknya elemen di dalam himpunan A.
Saya akan merubah cerita soal tersebut sehingga tidak terlalu matematis. Misalkan array X menampung tinggi badan orang dalam sebuah barisan, dari paling depan hingga paling belakang. Setiap orang di barisan menghadap ke depan. Orang di barisan ke-i dapat melihat orang di barisan ke-j, apabila semua orang yang berada di antara i dan j (termasuk i dan j) lebih pendek atau sama dengan tinggi orang ke-i. Lalu S[i] akan menunjukkan banyaknya orang yang dapat dilihat orang ke-i. Nah tugas kita berikutnya adalah menghitung nilai dari (S[1] + S[2] + ... + S[n]) mod m.
Langkah pertama adalah membuat array X sesuai dengan nilai n dan m yang diberikan. Hal ini dapat anda lakukan dengan membangkitkan daftar bilangan prima terlebih dahulu, menggunakanSieve of Eratosthenes . Anda cukup mencari hingga bilangan prima ke-100000.
Setelah itu, barulah kita memasuki permasalahan utamanya. Misalnya kita hendak mencari berapa banyak orang yang dapat dilihat oleh orang ke-a. Cara yang paling mudah adalah melakukan segalanya apa adanya: ambil i = a, selama X[a] > X[i], kurangi i dengan 1. Hingga suatu saat X[a] < X[i], maka diketahui bahwa orang ke-i adalah orang pertama yang tidak bisa dilihat oleh orang ke-a. Kita sebut orang ini adalah "penutup" dari orang ke-a. Selain itu, kita juga bisa menyimpulkan bahwa S[a] = a - i. Dengan cara ini, kita mendapatkan algoritma \(O(N^2)\). Berhubung N bisa mencapai 100000, maka dipastikan mendapat TLE.
Untuk solusi optimal, diperlukan beberapa observasi:
Observasi 1:
Jika orang ke-b adalah penutup dari orang ke-a, maka tidak mungkin ada orang ke-c, dimana b < c < a dan X[c] ≥ X[b]. Pernyataan ini dapat dibuktikan dengan mudah melalui coret-coret di kertas.
Observasi 2:
Semua orang ke-x (x < a) yang lebih pendek atau tingginya sama dengan orang ke-a tidak penting. Mereka tidak mungkin menjadi penutup bagi a, maupun penutup bagi orang-orang di belakang a. Jadi, orang-orang yang penting adalah semua orang ke-x (x < a) yang lebih tinggi dari orang ke-a.
Berdasarkan observasi itu, maka calon-calon dari penutup dapat kita simpan dalam stack yangstrictly-decreasing , atau elemen-elemennya menurun dari besar ke kecil. Selama orang ke-a lebih tinggi dari orang yang paling pendek dari stack, keluarkan orang yang paling pendek itu dari stack (karena dia tidak penting, berdasarkan observasi 2). Ketika orang terpendek di stack (sebut saja orang ke-b) sudah lebih tinggi dari orang ke-a, maka orang ke-b adalah penutup dari a. Kini, orang ke-a menjadi calon penutup bagi orang-orang di belakang a, sehingga a dimasukkan ke dalam stack.
Setiap orang paling banyak masuk ke dalam stack sebanyak 1 kali, dan paling banyak keluar dari stack sebanyak 1 kali. Sehingga maksimal ada 2*N operasi pada stack itu, dan kompleksitas solusi \(O(N)\).
Saya akan merubah cerita soal tersebut sehingga tidak terlalu matematis. Misalkan array X menampung tinggi badan orang dalam sebuah barisan, dari paling depan hingga paling belakang. Setiap orang di barisan menghadap ke depan. Orang di barisan ke-i dapat melihat orang di barisan ke-j, apabila semua orang yang berada di antara i dan j (termasuk i dan j) lebih pendek atau sama dengan tinggi orang ke-i. Lalu S[i] akan menunjukkan banyaknya orang yang dapat dilihat orang ke-i. Nah tugas kita berikutnya adalah menghitung nilai dari (S[1] + S[2] + ... + S[n]) mod m.
Langkah pertama adalah membuat array X sesuai dengan nilai n dan m yang diberikan. Hal ini dapat anda lakukan dengan membangkitkan daftar bilangan prima terlebih dahulu, menggunakan
Setelah itu, barulah kita memasuki permasalahan utamanya. Misalnya kita hendak mencari berapa banyak orang yang dapat dilihat oleh orang ke-a. Cara yang paling mudah adalah melakukan segalanya apa adanya: ambil i = a, selama X[a] > X[i], kurangi i dengan 1. Hingga suatu saat X[a] < X[i], maka diketahui bahwa orang ke-i adalah orang pertama yang tidak bisa dilihat oleh orang ke-a. Kita sebut orang ini adalah "penutup" dari orang ke-a. Selain itu, kita juga bisa menyimpulkan bahwa S[a] = a - i. Dengan cara ini, kita mendapatkan algoritma \(O(N^2)\). Berhubung N bisa mencapai 100000, maka dipastikan mendapat TLE.
Untuk solusi optimal, diperlukan beberapa observasi:
Observasi 1:
Jika orang ke-b adalah penutup dari orang ke-a, maka tidak mungkin ada orang ke-c, dimana b < c < a dan X[c] ≥ X[b]. Pernyataan ini dapat dibuktikan dengan mudah melalui coret-coret di kertas.
Observasi 2:
Semua orang ke-x (x < a) yang lebih pendek atau tingginya sama dengan orang ke-a tidak penting. Mereka tidak mungkin menjadi penutup bagi a, maupun penutup bagi orang-orang di belakang a. Jadi, orang-orang yang penting adalah semua orang ke-x (x < a) yang lebih tinggi dari orang ke-a.
Berdasarkan observasi itu, maka calon-calon dari penutup dapat kita simpan dalam stack yang
Setiap orang paling banyak masuk ke dalam stack sebanyak 1 kali, dan paling banyak keluar dari stack sebanyak 1 kali. Sehingga maksimal ada 2*N operasi pada stack itu, dan kompleksitas solusi \(O(N)\).
Tidak ada komentar :
Posting Komentar