Desain Dan Analisis Algoritma Meet In The Middle Pada Permasalahan E-OLYMP 9088 Xor Path.

Darwati, Qatrunada Qori (2022) Desain Dan Analisis Algoritma Meet In The Middle Pada Permasalahan E-OLYMP 9088 Xor Path. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000059-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (3MB)

Abstract

Permasalahan dalam Tugas Akhir ini adalah "XOR path" pada situs penilaian daring E-Olymp dengan nomor soal 9088. Permasalahan ini meminta keluaran berupa biaya penelusuran terkecil jalan dari sel di kiri atas, yaitu sel (1,1) menuju sel di kanan bawah, yaitu sel (N,N) pada suatu matriks berukuran N×N. Biaya penelusuran adalah hasil operasi bitwise Exclusive OR (XOR) antara elemen matriks dari sel yang dikunjungi. Penelusuran jalan dalam permasalahan hanya bisa bergerak ke kanan atau ke bawah. Karena titik awal dan titik akhir jalan tersebut diketahui, penelusuran jalan dapat dilakukan menggunakan algoritma Meet in the Middle. Algoritma Meet in the Middle akan membagi penelusuran menjadi dua bagian yaitu penelusuran dari titik awal dan penelusuran dari titik akhir. Masing-masing penelusuran ini diselesaikan kemudian digabungkan kembali untuk mendapatkan biaya penelusuran terkecil. Penggunaan algoritma Meet in the Middle berhasil menyelesaikan permasalahan XOR path secara efisien dengan rata-rata waktu 0,2626 detik dan penggunaan memori 8.601 KiB. Solusi permasalahan berhasil menempati peringkat pertama pada situs E-Olymp Online Judge.
=================================================================================================================================
The problem in this Final Project is “XOR path” which can be found on the online assessment site E-Olymp with problem number 9088. The problem asks to find lowest possible path cost where the path starts from cell (1,1) to cell (N,N) of a N×N matrix. The cost of the path is calculated using bitwise Exclusive OR (XOR) operation. The path can only move down and to the right. The source vertex and the destination vertex of the path in this problem is known so the search of the path to find the lowest possible path cost can be done using Meet in the Middle algorithm. Meet in the Middle algorithm splits the search into two, namely the search from source vertex and the search from destination vertex, solves them individually, and then merge them. The use of Meet in the Middle algorithm has been succeded in solving “XOR path” problem efficiently with an average time of 0,2626 seconds and memory usage of 8.601 KiB. Solution of the problem ranks first in the E-Olymp Online Judge site.

Item Type:	Thesis (Other)
Additional Information:	RSIf 519.5 Dar d-1 2022
Uncontrolled Keywords:	Divide and Conquer, Exclusive OR (XOR), Kombinatorika, Matriks, Meet in the Middle. Divide and Conquer, Exclusive OR (XOR), Combinatorics, Matrix, Meet in the Middle.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	25 May 2026 07:27
Last Modified:	25 May 2026 07:27
URI:	http://repository.its.ac.id/id/eprint/133408

Actions (login required)

View Item