Akbar, Mohammad Fany Faizul (2025) PERANCANGAN DAN ANALISIS PENERAPAN METODE LOWEST COMMON ANCESTOR PADA STUDI KASUS SPOJ 37375 KINGDOM OF EQUALITY. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5025201225-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5025201225-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (9MB) | Request a copy |
Abstract
Sphere Online Judge (SPOJ) adalah platform berbasis peramban yang berfokus pada sistempenilaian program dengan sekitar 13.000 permasalahan asli yang dirancang oleh komunitas ahli
pembuat soal. Salah satu permasalahan classical yang terdapat pada platform ini adalah Kingdom of Equality. Dalam studi kasus ini, terdapat sebuah kerajaan yang dapat
direpresentasikan sebagai sebuah forest dengan kota yang dianggap sebagai node-nya. Pada permasalahan ini diminta untuk menemukan jumlah kota yang memiliki jarak shortest path yang sama dan terjangkau dari kota-kota yang ditentukan. Adapun masalah yang muncul meliputi konektivitas kota, perhitungan jarak kota bernilai genap, perhitungan jarak shortest path, dan perhitungan jumlah kota yang memenuhi kriteria. Tugas Akhir ini menerapkan metode Lowest Common Ancestor untuk mencari jumlah node dengan jarak shortest path yang sama ke setiap node yang sudah ditentukan. Metode Lowest Common Ancestor dengan Binary Lifting digunakan untuk perhitungan jarak shortest path antar node. Pada implementasinya, diterapkan juga DFS sebagai algoritma penelusuran dan identifikasi pada forest serta Disjoint-set Forest untuk mengidentifikasi dan memeriksa konektivitas node. Solusi yang dirancang berhasil menyelesaikan permasalahan studi kasus Kingdom of Kequality dengan status accepted dan menempati peringkat 5 dari 11 pengguna yang menyelesaikan permasalahan ini pada Desember 2024. Solusi ini memiliki kompleksitas waktu preprocessing
=============================================================================================================================
The Sphere Online Judge (SPOJ) is a browser-based platform focused on a program evaluation system with approximately 13,000 original problems designed by a community of expert problem setters. One of the classical problems available on this platform is Kingdom of Equality. In this case study, there is a kingdom that can be represented as a forest, where cities are considered as nodes. The problem requires finding the number of cities that have the same shortest path distance and are reachable from the given set of cities. The challenges involved in this problem include city connectivity, determining even-valued distances between cities, shortest path computation, and counting the number of cities that meet the given criteria. This final project applies the Lowest Common Ancestor (LCA) method to determine the number of nodes with the same shortest path distance to each of the specified nodes. The Lowest Common Ancestor with Binary Lifting method is used for calculating shortest path distances between nodes. In its implementation, Depth-First Search (DFS) is utilized for traversing and identifying the forest structure, while the Disjoint-Set Forest is employed to identify and verify node connectivity. The proposed solution successfully solves the Kingdom of Equality case study problem with an "Accepted" status, ranking 5th out of 11 users who solved this problem as of December 2024. This solution has a preprocessing time complexity of
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | Binary Lifting, Lowest Common Ancestor, Shortest Path, Sphere Online Judge, Undirectional Graph, Binary Lifting, Lowest Common Ancestor, Shortest Path, Sphere Online Judge, Undirectional Graph. |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Mohammad Fany Faizul Akbar |
| Date Deposited: | 01 Feb 2025 04:52 |
| Last Modified: | 01 Feb 2025 04:52 |
| URI: | http://repository.its.ac.id/id/eprint/117397 |
Actions (login required)
 |
View Item |