Desain dan Analisis Penyelesaian Persoalan E-Olymp 24 Paint2D-Crack Menggunakan Metode Dynamic Programming

Musdalifah, Rofita Siti (2022) Desain dan Analisis Penyelesaian Persoalan E-Olymp 24 Paint2D-Crack Menggunakan Metode Dynamic Programming. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000034-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2024. Download (2MB) | Request a copy

Abstract

The problem in this thesis is "Paint2D-Crack" which can be found on the online assessment site E-Olymp with problem number 24. The problem asks to find the minimum steps to fill a square area using rectangular blocks with a predetermined size. This rectangular block is formed from the template block given at the beginning. In the filling process, there are several steps to fill the square area as much as possible. So it is necessary to find an efficient filling configuration so that filling can be optimal. This final project reviews the solution using Dynamic Programming to efficiently form the initial rectangle. In addition, this final project will explain spiral filling that optimize linear filling in certain cases. So that the minimum steps for compiling the most efficient configuration in a square area, are obtained.

Based on the test results from the given case study, the solution using the Dynamic Programming method requires an average time of 0.0037 seconds and an average memory of 533.2 KiB. This solution ranks second in the E-Olymp Online Judge site and received a grade A in terms of memory usage, which means it uses less resources than 90% of all solutions submitted.
================================================================================================
Permasalahan dalam tugas akhir ini adalah “Paint2D-Crack” pada situs penilaian daring E-Olymp nomor soal 24. Dalam permasalahan ini diminta mencari jumlah langkah minimal untuk mengisi suatu area persegi menggunakan persegi panjang dengan ukuran yang telah ditentukan, di mana persegi panjang ini dibentuk dari blok template yang diberikan di awal. Dalam proses pengisian terdapat beberapa ketentuan langkah untuk mengisi area persegi semaksimal mungkin. Sehingga diperlukan pencarian konfigurasi pengisian yang efisien agar pengisian dapat optimal. Tugas akhir ini mengulas penyelesaian menggunakan Dynamic Programming untuk membentuk persegi panjang awal dengan efisien. Selain itu, akan dibahas mengenai pengisian spiral untuk mengoptimasi pengisian secara linier pada kasus tertentu. Sehingga didapatkan langkah minimal pembentukan konfigurasi paling efisien pada pengisian blok pada area persegi.

Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan metode Dynamic Programming membutuhkan rata-¬rata waktu sebesar 0,0037 detik dan rata--rata memori sebesar 533,2 KiB. Solusi ini berhasil menempati peringkat kedua pada situs E-¬Olymp Online Judge dan mendapatkan grade A dari segi penggunaan memori, yang berarti solusi menggunakan lebih sedikit sumber daya dibandingkan 90% solusi lainnya.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	block, dynamic programming, filling, minimal steps, rectangular, langkah minimal, pengisian, persegi panjang
Subjects:	T Technology > T Technology (General) > T57.83 Dynamic programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Rofita Siti Musdalifah
Date Deposited:	10 Feb 2022 06:42
Last Modified:	10 Feb 2022 06:42
URI:	http://repository.its.ac.id/id/eprint/93511

Actions (login required)

View Item