Babak Keseluruhan

Ngoding Seru 2019 (tidak terhitung babak uji coba) diawali dengan soal Papan Permainan, yang dapat diselesaikan dengan memperhatikan berbagai kasus sederhana. andrewtheodore (Andrew Theodore) menjadi peserta pertama yang mendapatkan umpan balik ACCEPTED pada Ngoding Seru 2019 dengan menyelesaikan soal ini pada menit ketiga.

stevenwjy (Steven Wijaya) menjadi peserta pertama yang menyelesaikan seluruh soal pada babak ini pada menit ke-66. Seluruh peserta yang mendapatkan peringkat 50 besar pada babak ini dapat mengikuti babak 2 pada 16 Maret, 7PM WIB. Kami akan mengirimkan e-mail kepada seluruh peserta yang lolos ke babak 2 sebagai konfirmasi. Seluruh peserta yang tidak mendapatkan peringkat 50 besar pada babak ini dapat mengikuti babak 1B pada 9 Maret, 7PM WIB.

Credits:

  • Papan Permainan: Ditulis dan disiapkan oleh Jonathan Irvin Gunawan.
  • Persegi Panjang: Ditulis dan disiapkan oleh Wiwit Rifa'i.
  • Nilai Keindahan: Ditulis dan disiapkan oleh Wiwit Rifa'i.
Solusi dan persiapan komponen soal lainnya dan juga review oleh Ashar Fuadi, Jonathan Irvin Gunawan, Muhammad Ayaz Dzulfikar, dan Wiwit Rifa'i.
Penulis analisis:

Papan Permainan

Karena sebuah bidak hanya dapat berpindah ke petak yang nomor barisnya lebih besar daripada nomor baris petak awal, bidak yang awalnya diletakkan pada petak (A, B) tidak mungkin dapat berada di petak (X, Y) setelah satu atau lebih langkah jika A > X. Sebagai tambahan, karena nomor baris petak tempat bidak berada bertambah satu setiap langkah, maka bidak membutuhkan tepat X - A langkah untuk sampai ke baris X.

Dalam setiap langkah, bidak hanya dapat berpindah ke petak yang nomor kolomnya berselisih satu dengan nomor kolom petak awal. Karenanya, selisih nomor kolom petak tujuan dan nomor kolom petak awal tidak boleh lebih dari banyaknya langkah. Dengan kata lain, bidak yang awalnya diletakkan pada petak (A, B) tidak mungkin dapat berada di petak (X, Y) setelah satu atau lebih langkah jika |Y - B| > X - A.

Sebagai tambahan, jika kita asumsikan papan permainan ini sebagai papan catur (petak (i, j) berwarna hitam jika (i + j) genap, atau putih jika (i + j) ganjil), maka pada setiap langkah, bidak hanya dapat berpindah ke petak yang warnanya sama dengan petak awal. Karenanya, petak tujuan dan petak awal harus berwarna sama. Dengan kata lain, bidak yang awalnya diletakkan pada petak (A, B) tidak mungkin dapat berada di petak (X, Y) setelah satu atau lebih langkah jika (A + B) mod 2 ≠ (X + Y) mod 2.

Jika seluruh syarat di atas terpenuhi, maka bidak yang awalnya diletakkan pada petak (A, B) dapat berada di petak (X, Y) setelah satu atau lebih langkah.

Persegi Panjang

Subsoal 1

Subsoal ini dapat diselesaikan dengan pendekatan greedy yaitu dengan membentuk persegi panjang terluar terlebih dahulu sehingga titik-titik yang belum digunakan berada di dalam persegi panjang tersebut. Dengan begitu, setiap persegi panjang yang akan dibentuk selanjutnya pasti akan berada di dalam persegi panjang yang telah terbentuk.

Untuk membentuk persegi panjang terluar tersebut, kita harus mengecek apakah terdapat pasangan titik sudut kiri-atas dan kanan-bawah atau pasangan titik sudut kiri-bawah dan kanan-atas untuk membentuk persegi panjang tersebut. Titik sudut kiri-atas tersebut dapat dicari dengan mencoba semua titik yang belum digunakan dan mengecek apakah titik tersebut berada di sebelah kiri-atas dari semua titik lain yang belum digunakan. Titik-titik kanan-bawah, kiri-bawah, dan kanan-atas juga dapat dicari dengan cara serupa. Pencarian titik-titik tersebut dapat dilakukan dalam O(N2). Lalu jika pasangan titik pembuat persegi panjang tersebut ada, maka tandai pasangan titik tersebut sebagai sudah digunakan agar tidak dapat digunakan lagi dalam persegi panjang selanjutnya. Namun jika tidak ada, maka persegi panjang tersebut tidak mungkin dibentuk. Sehingga pembentukan semua persegi panjang dapat dilakukan dalam O(N3).

Solusi ini masih dapat dioptimasi lagi, yaitu untuk mencari titik sudut kiri-atas, kita hanya perlu mempertimbangkan satu kandidat titik yang mungkin. Titik kandidat yang paling mungkin untuk titik kiri-atas tersebut adalah titik yang dipilih berdasarkan koordinat Y teratas dan jika masih ada lebih dari 1 kemungkinan ambil titik dengan koordinat X terkiri. Lalu barulah lakukan pengecekan apakah titik tersebut memenuhi untuk menjadi titik sudut kiri-atas. Titik sudut kanan-bawah, kiri-bawah, dan kanan-atas juga dicari dengan cara serupa. Karena pencarian titik-titik tersebut menjadi O(N) maka kompleksitas keseluruhan menjadi O(N2).

Perlu diingat pula bahwa persegi panjang yang dibentuk harus memiliki luas positif.

Subsoal 2

Perhatikan bahwa jika pembentukan semua persegi panjang tersebut memang mungkin, maka hanya ada 1 kemungkinan hasil dari pembentukan tersebut. Misal jika kita urutkan koordinat X dari titik-titik tersebut, maka akan menjadi XP1 ≤ XP2 ≤ ... ≤ XPN dengan P adalah permutasi dari 1 sampai N. Dan misalkan juga jika kita urutkan koordinat Y dari titik-titik tersebut, maka akan menjadi YQ1 ≤ YQ2 ≤ ... ≤ YQN dengan Q adalah permutasi dari 1 sampai N.

Persegi panjang terluar ke-i akan memiliki sisi kiri pada koordinat X = XPi, sisi kanan pada koordinat X = XPN+1-i, sisi bawah pada koordinat Y = YQi, dan sisi atas pada koordinat Y = YQN+1-i. Sehingga pasangan titik pembentuknya adalah antara pasangan titik (XPi, YQi) dan (XPN+1-i, YQN+1-i) atau pasangan titik (XPi, YQN+1-i) dan (XPN+1-i, YQi). Jika kedua pasangan pembentuk tersebut ada, maka kita harus berhati-hati dalam memilih pasangan mana yang akan digunakan kerena bisa jadi di antara titik tersebut ada yang diperlukan untuk membentuk persegi panjang lain.

Kita bisa melakukan pendekatan greedy seperti pada Subsoal 1 yaitu membentuk persegi panjang dari luar. Kita bisa menggunakan struktur data Set untuk mengelola titik-titik yang belum digunakan. Untuk setiap persegi panjang dari yang terluar, cek apakah ada pasangan pembentuknya tadi. Jika ada, pilihlah pasangan manapun yang ada karena hasilnya akan sama saja, lalu hapus titik yang sudah digunakan dari Set. Jika tidak ada, berarti pembentukan persegi panjang tersebut tidak mungkin. Kompleksitas keseluruhan adalah O(N × log(N)). Sekali lagi, ingat bahwa persegi panjang yang dibentuk harus memiliki luas positif.

Nilai Keindahan

Subsoal 1

Subsoal ini dapat diselesaikan menggunakan dynamic programming. Mari kita definisikan fungsi f(x, y) (1 ≤ x ≤ N, 0 ≤ y ≤ max(A) sebagai jumlah B1 × B2 × ... × B|B| untuk semua B yang merupakan subhimpunan dari {A1, A2, ..., Ax} yang memenuhi FPB(B1, B2, ..., B|B|) = y.

f(x, y) dapat dihitung secara rekursif dengan menjumlahkan kedua kemungkinan kasus apakah Ax merupakan anggota B atau tidak.

  • Jika Ax bukan merupakan anggota B, maka jumlah B1 × B2 × ... × B|B| sama dengan f(x - 1, y).
  • Jika y habis membagi Ax, maka kita juga harus menghitung kemungkinan bahwa Ax merupakan anggota B. Jika Ax merupakan anggota B, maka jumlah B1 × B2 × ... × B|B| sama dengan jumlah dari f(x - 1, i) untuk semua 0 ≤ i ≤ max(A) yang memenuhi FPB(i, Ax) = y. Untuk optimisasi, kita dapat melakukan iterasi hanya nilai i yang merupakan kelipatan dari y.
Nilai f(x, y) merupakan jumlah dari dua kemungkinan tersebut.

Basis dari fungsi ini adalah:

  • f(x, 0) = 1, untuk semua 1 ≤ x ≤ N.
  • f(1, y) = 0, untuk semua 1 ≤ y ≤ max(A), y ≠ A1.
  • f(1, A1) = A1.

Jawaban yang diminta adalah jumlah dari f(N, i) × i untuk semua 1 ≤ i ≤ max(A). Kompleksitas waktu solusi ini adalah O(N × max(A) × log(max(A))).

Subsoal 2

Definisikan fungsi g(x) untuk 1 ≤ x ≤ max(A) sebagai jumlah B1 × B2 × ... × B|B| untuk semua B yang merupakan subhimpunan dari himpunan A sehingga x habis membagi FPB(B1, B2, ..., B|B|). Misalkan himpunan Kx adalah subhimpunan terbesar dari A sehingga elemen-elemennya habis dibagi oleh x. Karena seluruh subhimpunan dari Kx mencakup semua B yang valid, maka kita dapat menghitung nilai g(x) dengan:

g(x) = (Kx1 + 1) × (Kx2 + 1) × ... × (Kx|Kx| + 1) - 1

Lalu definisikan juga fungsi h(x) untuk 1 ≤ x ≤ max(A) sebagai jumlah B1 × B2 × ... × B|B| untuk semua B yang merupakan subhimpunan dari himpunan A yang memenuhi FPB(B1, B2, ..., B|B|) = x. Misalkan himpunan Mx adalah himpunan bilangan kelipatan dari x yang kurang dari atau sama dengan max(A) dan lebih dari x. Berdasarkan definisi dari g(x) dan h(x), maka nilai dari h(x) dapat dihitung dengan:

h(x) = g(x) - (h(Mx1) + h(Mx2) + ... + h(Mx|Mx|))

Perhatikan bahwa |Kx| dan |Mx| paling banyak adalah max(A)/x. Sehingga, penjumlahan dari |Kx| dan |Mx| untuk semua 1 ≤ x ≤ max(A) yaitu |K1| + |K2| + ... + |Kmax(A)| dan |M1| + |M2| + ... + |Mmax(A)|, keduanya tidak akan lebih dari max(A) × Hmax(A) dengan Hmax(A) adalah Harmonic number. Oleh karena itu, nilai dari g(x) dan h(x) untuk semua 1 ≤ x ≤ max(A) dapat dihitung dalam O(max(A) × log(max(A))) dengan mengiterasi semua kelipatan untuk setiap x.

Jawaban yang diminta adalah jumlah dari h(i) × i untuk semua 1 ≤ i ≤ max(A).