Saturday, May 10, 2014

ASIS Quals 2014 Write Up: Gas Stations (PPC 225)

Deskripsi tantangan:
We want to plan the placement of some gas stations, in such a way that cost of traveling between homes and nearest gas station be the least possible amount.
nc 87.107.124.13 9302
Kita diminta untuk menghubungi 87.107.124.13:9302 untuk memulai tantangan ini. Berikut adalah screenshot ketika kita terhubung ke sana.


Begitu kita mengirimkan "START" permainan dimulai. Kita diberikan jumlah gas station (k) dan 100 data point. Tujuannya adalah kita harus menentukan lokasi gas station yang optimal sehingga jarak menuju ke sana dari 100 data poin adalah minimum. Bayangkan kita diberikan koordinat (x,y) dari 100 rumah dan Operator Seluler ingin membangun sebanyak k BTS, dimana lokasi BTS harus dibangun sehingga sinyalnya bisa melayani pelanggan dengan optimal ?

Problem ini bisa diselesaikan dengan clustering data, yaitu mengelompokkan data menjadi k kelompok. Salah satu algoritma yang populer adalah K-Means. Jadi di tantangan ini saya memakai module python sklearn untuk memakai KMeans.

Berikut adalah snippet fungsi untuk mencari solusi optimal dari soal yang diberikan.



Berikut adalah screenshot ketika kita secara manual memasukkan solusi, sistem akan membalas dengan "Good" bila solusi optimal atau "Bad" bila tidak. Setelah itu sistem akan memberi soal yang baru dengan data point yang berbeda dan jumlah gas station yang berbeda juga. Kita diminta menyelesaikan semua soal yang diberikan secepat mungkin, jadi tidak mungkin dengan cara manual, harus dibuat script untuk melakukan itu.

Berikut adalah source code yang saya pakai untuk menyelesaikan tantangan ini.

Setelah script berjalan, mulai dari k=3 sampai k=9 (9 gas station), akhirnya kita berhasil mendapatkan flagnya "Congratulations! The flag is ASIS_a1db095f08bde77fbccc5b903a8329bb".

3 comments:

  1. Makasih Pak sudah di share write up nya buat belajar..
    Mas saya mau tanya soal tentang.
    Downtime caused to a website by massive referrals from another popular site
    itu jawabanya apa ya mas?
    makasih

    ReplyDelete
  2. There are tons of choices and most of them have reasonably stable rankings. Although it might replicate Vegas-style slot machines, there are not any money prizes. Slotomania’s focus is on exhilarating gameplay and fostering a happy global group. House of Fun does not require cost to entry and play, however it additionally permits you to buy virtual 1xbet korea gadgets with actual cash inside the sport. You can disable in-app purchases in your device's settings. You could require an internet connection to play House of Fun and entry its social features.

    ReplyDelete