Pembahasan Soal OSN Informatika/Komputer Tahun 2017

Nah berikut adalah pembahasan soal OSN tahun 2017 oleh tim. Pembahasan ini digunakan oleh tim resmi Scientific Committee OSN Informatika 2017.

1 1A : Pertahanan Pekanbaru

Soal ini ditulis oleh Alham Fikri Aji.

1.1 Subsoal 3

Subsoal ini dapat diselesaikan menggunakan complete search. Salah satu cara yang bisa digunakan adalah menggunakan rekursi; pada setiap lantai, coba semua kemungkinan pilihan yang tersedia, yaitu kabur melewati penjaga atau mengalahkan penjaga, lalu cari jumlah waktu minimal. Kompleksitas dari solusi ini adalah O(2^N).

1.2 Subsoal 4

Subsoal ini dapat diselesaikan menggunakan dynamic programming (DP). State dari DP tersebut adalah (posisi lantai, banyak lantai yang mana penjaganya sudah dikalahkan). Untuk mengisi nilai dari DP, cari hasil minimum dari kedua kemungkinan pilihan untuk setiap lantai. Kompleksitas dari solusi ini adalah O(N²).

1.3 Subsoal 5

Karena stamina dari Pak Dengklek, sang makhluk jahat, dan para penjaga tidak perlu diperhatikan, maka untuk setiap lantai, pilih nilai yang paling minimum di antara L[i] dan K[i]. Kompleksitas dari solusi ini adalah O(N).

1.4 Subsoal 6 

Subsoal ini dapat diselesaikan dengan bantuan sorting. Untuk setiap lantai ke-i, jika nilai L[i] ≤ K[i], maka L[i] pasti dipilih. Selain itu, anggap awalnya kita memilih K[i]. Misal ).  menyatakan stamina Pak Dengklek saat ini. Jika saat selesai ). < Sm, maka kita harus mengganti beberapa K[i] dengan L[i]. Dalam memilih yang diganti, prioritaskan yang memiliki nilai K[i]−L[i] paling besar. Hal ini bisa dicapai dengan bantuan sorting. Selanjutnya, kurangi total waktu dengan dengan Sm−).  nilai K[i]−L[i] terbesar (bisa dilihat bahwaini sama dengan menukar K[i] dengan L[i]). Kompleksitas dari solusi ini adalah O(NlogN). < Sm, maka kita harus mengganti beberapa K[i] dengan L[i]. Dalam memilih yang diganti, prioritaskan yang memiliki nilai K[i]−L[i] paling besar. Hal ini bisa dicapai dengan bantuan sorting. Selanjutnya, kurangi total waktu dengan dengan Sm−).  nilai K[i]−L[i] terbesar (bisa dilihat bahwaini sama dengan menukar K[i] dengan L[i]). Kompleksitas dari solusi ini adalah O(NlogN).

1.5 Subsoal 7

Subsoal ini dapat diselesaikan dengan bantuan priority queue. Solusi untuk subsoal ini tidak jauh berbeda dengan solusi subsoal 6, namun simpan K[i] − L[i] dalam priority queue. Untuk setiap lantai ke-i, selama ). < P[i], maka cari nilai terbesar dari priority queue tersebut dan kurangi total waktu dengan nilai tersebut. Lakukan hal yang sama selama ). saat Pak Dengklek berada di lantai N masih lebih kecil dari Sm. Kompleksitas dari solusi ini adalah O(NlogN).

Nah itulah pembahasan soal sampai dengan subsoal 7. Jika sobat berminat, bisa mengunduhnya disini (sumber : https://osn.toki.id)

Terimakasih telah berkunjung ke blog kami, semoga bermanfaat. Jika ada salah dalam penulisan dan lain sebagainya, sobat bisa meninggalkan komentar untuk evalusai post kami atau dengan cara meng-email ke : mustakimhusaini69@gmail.com.