My Journey : OpenOSN 2011 Day 2

Alhamdulillah, itulah kata kesekian yang ku ucapkan ketika kompetisi Open OSN ini berakhir. 5 jam penuh aku duduk di depan komputer dengan sekali ke kamar mandi.

Berikut ini adalah penjelasan dari soal-soal Sesi 3 OSN 2011 :

Soal 1 : Tiang Pemancar
Menurutku soal ini adalah yang paling mudah di Sesi 3 ini, makanya aku kerjakan paling awal. Pertama kali mikir sih memang pusing bener, tapi setelah tau kalo yang paling penting itu Titik sudut siku-sikunya.  Jadi ada inspirasi buat solve cepet.

Setiap titik di koordinat kita looping, trus kita cari berapa banyak yang koordinat X nya sama, anggap aja itu NX dan kita cari berapa banyak yang koordinat Y nya sama, anggap aja itu NY. Dengan satu titik sudut siku-siku itu, bisa kita temukan banyak segitiga siku-siku yang bisa dibentuk dengan (NX-1)*(NY-1). Trus kita jumlah deh di setiap loopnya.. Gampang kan. 😀

My Score : 100 (AC)
My Solution is here. (100) (AC).
Soal 2 : Radar Pesawat
Pertama kali liat, kayaknya ini soal paling sulit di sesi 3 ini, makanya aku cuma nyampah 1 paket testcase. Tapi setelah kontes usai, katanya mas alpan ternyata ini mudah, Special case nya itu kalo ada beberapa pesawat yang T ama V nya sama semua. Kalo semua pesawat T dan V nya berbeda, bisa hanya dengan 1 radar. Kalo semua T dan semua V sama juga gampang tinggal output (N+1)/2 aja. Selebihnya agak rumit. Hahaha.

My Score : 15
My Solution : Coming Soon

Soal 3 : Bebek Istimewa
Soal ini mungkin yang paling mudah kedua. Kalo aku sih tinggal di proses pake Bottom Up DP di matrix boolean (Nkandang*NLangkah) aja, tapi skornya cuma 90. Karena pada paket testcase terakhir, udah pasti Memory Limit karena arraynya berjuta-juta. Cara yang lain yaitu pake Top Down DP, yang kayaknya bisa  AC di paket testcase terakhir. Atau malah bisa pake DFS atau BFS, trus kita telusuri langkahnya.

My Score : 90 (Memory Limit Exceeded)
My Solution is here. (90) (MLE)

Soal 4 : Bongkar Sandi
Sebenarnya soal ini ga terlalu sulit. Cukup output 000000, 111111, …, 999999 trus itung berapa kemunculan angka itu dan cari gimana biar mem-permutasikan secara efisien hingga bisa nebak. Waktu kontes sama sekali nggak kepikiran cara ini & males banget buat mikir. Jadi cuma aku output 00,01,02.. ampe 99 aja (nyampah), lumayan sih bisa dapet nilai 30 :D.

My Score : 90
My Solution : Coming Soon.

Buat yang mau Soal Sesi 3 ini, bisa diliat di sini. Sebentar lagi pasti akan di publish di Toki LC.