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".