OSN tinggal lagi sebulan. Aku sadar bahwa ada pembahasan resmi OSN 2015 dan 2017, tapi gaada yang 2016 :(. Terutama ada soal super asik "wisata palembang" yang dimana orang yang AC setelah dua tahun ini baru dua orang (sekarang 3, karena ada aku :v). Jadi aku buat pembahasan OSN 2016. Mungkin soalnya udah basi(:v) tapi mudah-mudahan masih dapat dijadikan pembelajaran.
Catatan:
Aku engga ngeshare source codeku, karena implementasi itu bagian serunya. Tapi bakal ada beberapa pseudocode, aku tulis menggunakan bahasa pseudopascal :v.
Day 1
Pasar 16 Ilir
Subtask 1-6,8 (67 poin)
Perhatikan bahwa N*M paling banyak 20, cukup kecil jadi kita bisa buat semua kemungkinan jalannya. Kita asumsikan kasus terburuk, yaitu N*M=20. ini akan maksimum ketika R=4 dan C=5 (atau sebaliknya). Jadi banyaknya kemungkinan jalan cukup sedikit. Kita bisa simpan semua kemungkinan jawabannya dalam array, dan apabila ditanya harga antar P dan Q tinggal iterasi saja isi arraynya.
Nah, sekarang tinggal gimana caranya generate semua kemungkinan? pake teknik backtracking. Jadi kamu mulai dari titik (0,0), simpen array global yang nandain petak udah divisit atau belum, lalu coba visit. apabila udah sampai titik (n,m), masukin total sum sekarang ke array jawaban. Kurang lebih pseudocodenya kaya gini:
visited <- array boolean berukuran 36 x 36
value <- array berukuran 36x36, nilai dari matriks
sum <- sebuah integer
nilai <- sebuah array yang menampung harga-harga yang mungkin.
function backtrack(x,y : integer)
begin
if(visited(x,y)=FALSE)
begin
visited(x,y):=true;
sum:=sum+value(x,y);
if((x=N)AND (y=M)) //masukin sum ke dalam array nilai
else begin
backtrack(x+1,y);
backtrack(x,y+1);
backtrack(x-1,y);
backtrack(x,y-1);
end;
sum:=sum-value(x,y);
visited(x,y)=false;
end;
end;
Subtask 1-8 (100 poin)
Masalah dari algoritma sebelumnya adalah pencarian nilai diantara P dan Q bisa O(logn).
Kalau misal array nilai kita sudah sorted, kita bisa mencari banyaknya elemen diantara P dan Q dalam log n menggunakan binary search. Jadi, setelah mendapatkan array jawaban dengan backtracking, arraynya di sort dengan algo sorting nlogn lalu dijawab menggunakan binary search.
Taming a Bomb
Subtask dengan Bomb tipe-0 (37 poin)
Kita bisa coba tekan 1 sampai N secara berurutan, lalu N sampai 1 secara berurutan. lalu, selama belum terdengar "BIP" dua kali, tekan tombol acak. Jadi kurang lebih penekanan tombol kita kelihatan seperti ini:
1 2 3 4 5 ... N
N N-1 N-2 ... 3 2 1
X X X X X (untuk suatu X acak).
Kita juga mencatat kapan terdengar BIP pertama (sebut T1) dan BIP kedua (sebut T2). misal juga tombol targetnya adalah A, dan delaynya T.
Pada baris pertama, tombol bernomor i akan ditekan pada waktu ke-i. didapat persamaan A + T = T1.
Pada baris kedua, tombol bernomor i akan ditekan pada waktu ke-2N-i+1. didapat persamaan 2N-A+1+T=T2 -> T-A = T2-2N-1.
karena dua persamaan tersebut memiliki ruas kanan konstanta, jadi dua persamaan tersebut merupakan sistem persamaan dua variabel. Diselesaikan didapat A = (T1-T2+2N+1)/2. Berikutnya tinggal dipencet terus A sampai berhasil :).
Algo ini memerlukan 3N pemencetan dalam kasus terburuk untuk mendapat 2 BIP, ditambah kasus terburuk 2N pemencetan setelah nilai A ketemu. total dibutuhkan paling banyak ~5N pemencetan.
Subtask dengan bomb tipe-0 dan tipe-1 (100 poin)
Masalah pada algo sebelumnya adalah apabila bombnya tipe 1 dimana nilai A dan Knya kecil. misal A=1 dan K=1. maka menggunakan algo sebelumnya bomb akan keburu meledak sebelum BIP kedua terdengar.
Salah satu solusi yang mungkin menggunakan algoritma diatas adalah menanyakan permutasi 1-N secara acak dan pada giliran berikutnya menanyakan kebalikan dari permutasi tersebut. Sebagai contoh apabila n=7, kamu bisa nyoba nanya
7 3 2 4 3 1
1 3 4 2 3 7
X X X X X X (untuk suatu X acak)
persamaannya tinggal dimodif dikit, disini A=(T1-T2+2N+1)/2 maksudnya bukan berarti tombol jawabannya adalah A, melainkan A=tombol ke-i dalam permutasi tersebut. Jadi misal didapat A=3 menggunakan permutasi diatas, maka tombol jawabannya adalah 2.
Memang, solusi ini tetap bisa gagal, tapi peluangnya kecil dan layak dicoba apabila merasa beruntung :)
Kalau kamu orangnya ga percaya keajaiban kaya aku, tenang, ada solusi pastinya kok:
Jadi masalahnya adalah jaraknnya yang kepanjangan apabila nilai Knya kecil. Jadi kenapa ga kita bagi dua aja arraynya? misal kita coba solve 1..N/2 dan N/2..N secara terpisah (asumsi N genap, apabila ganjil, jadikan genap dan apabila ga ketemu jawabannya maka jawabannya bilangan yang ga kepilih).
Jadi kita pertama cari tau apakah jawabannya ada di antara 1..N/2.
kita tanya
1 2 3 ... N/2
N/2 N/2-1 ... 3 2 1
X X X X (untuk suatu X acak)
Yay, dengan begini, bomb tidak akan meledak karena pasti dua buah BIP berjarak tidak lebih dari N :D. Karena BIP pertama pasti muncul setelah minimal 3N/2 penekanan, kita bisa pruning apabila setelah 3N/2 penekanan BIP belum juga terdengar, maka jawabannya bukan pada range ini.
tunggu dulu... worst case pertanyaanya apabila Knya gede, didapat banyaknya pertanyaan 3N/2 + 3N/2 untuk bertanya dua range, ditambah 2N (asumsi K=N-1) untuk menjawab apabila tombol sudah ketemu. Jadi total pertanyaannya 7N dan tidak akan lolos subtask terakhir.
OH KALAU GITU DIBAGI 3 AJA RANGENYA, COBA TANYA 1..N/3 ,N/3+1..2N/3, 2N/3+1..N.
-orang yang bilang ternary search lebih cepet dari binary search.
hmm, tadi kalau ga dibagi, butuh 4N pertanyaan, dibagi dua butuh 6N, jadi kalau dibagi 3, bakal naik dong :(.
Balik ke bagi dua tadi, ternyata kita cuman perlu optimisasi N pertanyaan. Ternyata optimisasinya bertanyanya cukup digabung aja. jadi tanyanya
1 2 3 ... N/2
N/2 N/2-1 ... 3 2 1
N/2+1 N/2+2 ... N
N N/2-1 ... 1
X X X X X
worst case banyaknya pertanyaan, untuk mencari tombol dibutuhkan 3N, ditambah untuk jawab 2N, jadi pas 5N :) (sebenernya kurang dikit sih... soalnya aku banyak estimasi).
Pos Wisata Sungai
Subtask 1-9 (100 poin)
Ada properti operasi XOR sebagai berikut: Apabila kita punya suatu bilangan biner A, hanya ada tepat 1 bilangan B dimana A xor B = C.
Maka dari itu, Seandainya kita sudah menentukan nilai W1,W2,...W(n-1) dan bilangan biner yang kita dapat adalah A, kita harus memilih Wn sedemikian rupa sehingga A XOR Wn memiliki K buah bit 1. Dengan kombinasi didapat banyaknya bilangan biner dengan N digit dan K buah bit 1 adalah C(M,k). menggunakan properti XOR diatas, untuk setiap bilangan biner yang mungkin jadi jawaban, hanya ada 1 buah Wn yang memenuhi A XOR Wn = bilangan tersebut. Jadi banyaknya Wn yang memenuhi ada sebanyak C(M,k) pula.
Nah sekarang tinggal W1 sampai W(n-1) secara sembarang. Ini sama dengan mencari banyaknya bilangan biner M digit yang mungkin, yaitu 2^M. Karena ada (n-1) bilangan, maka totalnya ada (2^M)^(N-1) kemungkinan. rumus akhirnya menjadi 2^(M*(N-1)) * C(M,K).
Masalah yang mungkin muncul adalah gimana caranya menghitung C(M,K) modulo 10^9+7, karena ada pecahan faktorial. Perlu diketahui bahwa 1/n mod P = n^(P-2) mod P untuk suatu P bilangan prima (fermat's little theorem). solusinya adalah semua inverse factorial dan factorial bisa di precomputasi dengan O(N) dengan cara berikut:
f <- f[i] = nilai dari i! mod 10^9+7
inv <- inv[i] = nilai dari 1/i! mod 10^9+7
for i :=1 to 1000000 do
begin
f[i]:=f[i-1]*i mod 10^9+7;
inv[i]=inv[i-1]*(i ^ (10^9+5)) mod 10^9+7;
end;
untuk operasi pemangkatan, bisa gunakan pemangkatan DNC log(n).
Untuk soal ini, aku mohon maaf karena langsung solusi AC, aku udah coba-coba cari solusi non ac untuk subtask yang lebih kecil, namun selalu saja observasinya trivial dan mudah ditingkatkan agar jadi solusi AC :"
DAY 2
Robot Pempek
Subtask 1-5 (59 poin)
Misalkan D(A,B) menyatakan jarak manhattan dari titik A ke titik B. Kita juga nomori tempat pemancingannya dengan nomor 1 sampai N.
Misal pergerakan robot adalah C1,C2,C3,...,CM, dimana Ci menyatakan suatu titik pemancingan. Jelas bahwa D(C1,C2) > D(C2,C3) > D(C3,C4) > ... > D(C(M-1),CM).
Apabila semua tempat pemancingan kita jadikan vertex dalam suatu directed graph, dimana edge yang menghubungkan vertex i ke vertex j menyatakan bahwa apabila robot berada di vertex i maka pergerakan selanjutnya adalah ke vertex j. Jelas bahwa banyaknya edge yang keluar dari suatu vertex maksimal 1.
Sebuah cycle dengan panjang N didefinisikan sebagai serentetan vertex {V1,V2,V3,...,VN} dimana ada edge yang menghubungkan Vi dan V(i+1) untuk 1<=i<N dan VN dan V1.
Observasi: panjang cycle maksimum dari graph yang terbentuk maksimal 2.
Bukti:
misal ada cycle dengan panjang lebih dari 2. misal cycle tersebut sepanjang N dengan vertex {V1,V2,V3,...,VN}. Karena ada edge dari VN ke V1, maka D(V1,VN) < D(V(N-1),VN). Dari observasi pergerakan robot, didapat D(V1,V2) > D(V(N-1),VN). Maka setelah mensubstitusi D(V(N-1),VN) pada kedua persamaan, didapat D(V1,V2) > D(V1,VN). ini artinya apabila robot ada di V1, dia akan lebih memilih ke VN daripada ke V2. Sebuah kontradiksi. (terbukti).
Jadi graphnya kurang lebih berbentuk seperti ini:
Jadi, pertama kita precompute tempat pemancingan terdekat untuk setiap tempat pemancingan (looping aja, O(K^2)) misal nxt[i] adalah indeks tempat pemancingan yang berikutnya bakal divisit robot apabila robot berada pada tempat pemancingan ke-i atau bernilai -1 apabila ada lebih dari dua tempat pemancingan dengan jarak sama dari tempat pemancingan ke-i. Lalu bisa diaplikasikan dynamic programming.
dp[pos][last] -> tempat berhentinya robot, apabila robot berada pada tempat pemancingan ke-pos dengan tempat pemancingan terakhir yang dikunjungi robot adalah tempat pemancingan ke-last.
Transisi:
dp[pos][last] = pos (apabila nxt[i]=-1 atau nxt[i]=pos)
dp[pos][last] = dp[nxt[pos]][pos] (apabila tidak)
DP ini bekerjan dalam O(K^2). Untuk setiap query, cukup cari tempat pemancingan terdekat dari query tersebut dengan iterasi O(K). Total kompleksitas solusi: O(K^2 + QK).
Subtask 1-6 (76 poin)
Kendalanya adalah pada subtask ini, Q bisa mencapai 300000. Jadi pada saat menjawab query, kita bakal TLE saat mencari tempat pemancingan terdekatnya. Jadi dalam mencari tempat pemancingan terdekatnya, harus dilakukan optimisasi.
Optimisasinya adalah melakukan BFS Pararel dari setiap tempat pemancingan. Yakni, kita push semua tempat pemancingan kedalam queue secara bersamaan, lalu tandai suatu petak sebagai visited dengan tempat pemancingan terdekatnya adalah tempat pemancingan yang sedang di proses. Apabila ternyata sebuah titik memiliki dua atau lebih tempat pemancingan terdekat dengan jarak sama, tandai tempat tersebut dengan -1.
Ini bisa TLE karena setiap titik berpotensi divisit lebih dari sekali (bisa K kali!) jadi caraku mengatasinya adalah melakukan deepening bfs secara manual. Yakni, selama jarak yang dalam front queuenya sama, di proses saja, namun state selanjutnya tidak langsung di push kembali kedalam queue tersebut, melainkan ke sebuah stack. Nanti, ketika semua state dengan jarak X telah diproses, baru dipindahkan seluruh isi stack kedalam queue, namun, apabila suatu titik sudah dimasukkan kedalam queue dan masih ada state dengan titik itu lagi di dalam stack, maka titik kedua itu di ignore. Karena state dengan suatu titik yang mengandung nilai -1 pasti dimasukkan lebih akhir (artinya bakal masuk lebih awal ke queue, ingat stack LIFO), maka dijamin bahwa state itulah yang masuk kedalam queue. Dengan itu, kita menjamin bahwa setiap titik akan divisit tepat sekali, dan total prekomputasi jarak terdekat untuk setiap titik yang bukan tempat pemancingan berjalan dalam O(NM).
Untuk query, apabila yang di query tempat non pemancingan, bisa gunakan hasil precomputasi diatas, apabila tidak cukup jalankan seperti subtask sebelumnnya. DP masih sama seperti sebelumnya. Kompleksitas solusi (O(K^2 (DP,precompute nxt[i]) + MN (precompute non tempat pemancingan)).
Subtask 1-7 (100 poin)
Optimisasi terakhir yang perlu dilakukan agar solusinya accepted adalah precompute tempat pemancingan terdekat dari suatu tempat pemancingan. Kita tidak bisa menggunakan BFS pararrel karena bfs harus "menembus" titik yang sudah visited.
Ternyata, solusinya adalah cukup BFS biasa dari setiap tempat pemancingan, apabila ketemu sebuah tempat pemancingan lain, maka break dan tandai tempat pemancingan tersebut sebagai terdekat. Apabila ada lebih dengan jarak sama, maka tandai tempat itu sebagai -1.
Ini enggak bakal TLE, karena logikanya semakin banyak tempat pemancingannya, BFS akan semakin cepat selesai dan worst casenya adalah apabila ada dua buah tempat pemancingan, satu di pojok kiri bawah, dan satu di pojok kanan atas. Jadi kompleksitas total dari K BFS ini adalah O(MN).
DP kita juga harus dimodifikasi.
DP[i] -> tempat pemancingan terakhir, apabila robot berada di tempat pemancingan ke-i.
Ingat kembali bahwa graph tersebut memiliki panjang cycle maksimal dua, maka kita cek apakah posisi sekarang merupakan suatu cycle. Apabila tidak, maka dijamin kita akan bergerak lurus dan tidak akan pernah melewati titik-titik yang sudah pernah dilewati sebelumnya. kurang lebih seperti ini:
DP[i] = i (apabila nxt[i]=-1)
DP[i] = nxt[i] (apabila nxt[nxt[i]]=i)
DP[i] = DP[nxt[i]] (else)
Jadi total kompleksitas DPnya pun jadi O(K) doang.
Total kompleksitas : O(MN + K)
Belanja Suvenir
Subtask 1-5 (54 poin)
Perhatikan bahwa apabila ada solusi dengan M=X, maka pasti ada solusi dengan M=i (dimana i<X), dan apabila tidak ada solusi dengan M=X, maka pasti tidak ada solusi dengan M=i (dimana i>X). Jadi, kita bisa binary search jawabannya. Yakni, set sebuah lowerbound dan upperbound. lalu cari midnya. Apabila ada solusi untuk M=mid, maka pasti ada solusi untuk <mid, jadi lowerboundnya kita naikkan jadi mid. Apabila tidak, maka upperboundnya kita turunkan jadi mid-1. Pseudocode
left:=1,right:=2000000;
while(left<right)
begin
mid:=(left+right)/2;
if(ada solusi untuk M=mid) left:=mid;
else right:=mid-1
end;
//jawaban = left;
Nah sekarang tinggal gimana caranya ngecek apakah ada jawaban untuk M=mid. caranya adalah cukup coba semua kemungkinan mulai belanjannya kwik dan kwak, yakni misal kwik mulai belanja pada toko ke-i, dan kwak pada toko ke-j. Apabila semua suvernir berbeda, maka valid. Untuk ngeprint jawaban apabila ada jawaban dapat dilakukan dengan cara serupa. Kompleksitas untuk sekali cek adalah O(n^3). karena binary search, ditambah O(logn). total kompleksitasnya O(n^3 log n).
Subtask 1-7 (100 poin)
Mengecek valid untuk suatu M dapat dipercepat. dengan teknik sliding window. Jadi, kita coba apakah segmen [1,M],[2,M+1],[3,M+2],... bisa menjadi jawaban secara beruntun. Untuk mengecek apakah suatu segmen [X,Y] bisa menjadi jawaban, kita buat array freq[] dimana freq[i] menyatakan frekuensi banyaknya elemen pada segment tersebut. Jawaban valid apabila untuk semua i, freq[i]<=1.
Kita bisa masukkan semua nilai di segmen [1,M] kedalam array. Lalu perhatikan ketika kita mau cek segment [2,M+1], kita tidak perlu membuat array freq[] dari awal. Cukup "hapus" elemen ke-1 dari freq, dan "tambahkan" elemen ke-(M+1) ke freq. Jadi kita bisa cek apakah sebuah segment selanjutnya valid dalam O(1). Untuk mengecek apakah untuk semua i, freq[i]<=1, cukup maintain sebuah variabel yang menyatakan banyaknya elemen dalam freq[i] yang >1, dan update sejalan dengan array freq[]. Kompleksitasnya O(n log n).
Wisata Palembang
ini dia :) menurutku ini soal keren dan aku bangga bisa jadi orang kedua di Indonesia dan ketiga dunia yang bisa mensolve problem ini dengan fullscore :D.
Subtask 1-5 (43 poin)
Untuk soal ini, diperlukan suatu konsep yaitu "randomization". Jadi, untuk mensolve subtask ini, kita perlu menggenerate random graph, lalu mengecek apakah memenuhi kriterianya dan apabila tidak, coba generate baru lagi sampai ketemu. Setiap bahasa pasti mempunyai suatu library yang generate random numbers (rand() kalau C++, random kalau pascal). Pseudocode generate random graph
a <- sebuah array dua dimensi yang dimana a(i,j) nyimpen nilai dari panjang jalan (i,j)
for i :=1 to n
for j:=i+1 to n
a(i,j) := a(j,i) := random(L); //milih 1 bilangan acak dengan jangkauan 1 sampai L.
Lalu cek apakah graphnya valid dengan cara bruteforce (n!). apabila tidak, ulangi lagi. (looping while(true)).
Solusi ini akan mengenerate jawaban untuk subtask 1 sampai 5 dengan cukup cepat (hampir instan).
Karena ini solusi output only, jadi jawaban pada subsoal ini dapat disimpan, dan penghitungan nilai pada subsoal berikutnya dilakukan secara terpisah :).
Subtask 6-8 (0-57 poin, tergantung kesabaran)
Berapa banyak jalan berbeda maksimal yang dapat kita bentuk apabila kita punya N lokasi (termasuk hotel?). Jawabannya adalah (N-1)!/2. Karena hotel (lokasi ke 0) selalu berada di awal dan akhir wisata. dan (N-1) sisanya bebas dikunjungi dengan urutan apapun. Tapi dikarenakan pengunjungan simetris (i.e, ngunjungin 1-2-3 pasti memiliki sum sama dengan 3-2-1) maka banyaknya sum berbeda maksimal kita bagi 2 dan didapat (N-1)!/2.
Nah apabila kita perhatikan nilai M yang diminta pada 3 subtask terakhir ini, nilai M = (N-1)!/2 :O. Jadi diminta nilai sum yang tepat sama dengan jumlah maksimal yang dapat dibentuk. Algo random diatas memiliki peluang yang terlampau kecil untuk bisa mendapatkan jawaban, tahun lalu aku sudah coba seharian jalanin dan tidak ketemu jawabannya. Jadi, yang kita butuhkan adalah algo yang lebih baik dalam mencari jawabannya.
Masalah dari algo random diatas adalah, dia tidak peduli seberapa dekatnya kita terhadap jawaban, hanyalah bahwa jawabannya ketemu atau tidak. Contohnya, ambil testcase dimana M=2520. Algo random tersebut mungkin saja beberapa kali menemukan graph dengan M=2518 atau 2519, tapi tetap saja tidak bakal dihiraukan apabila jawabannya tidak tepat M=2520. Jadi? kenapa engga kita "membangun" solusi optimalnya dari solusi-solusi yang sudah ada?
Memperkenalkan : Genetics algorithm
intinya, kita menyimpan suatu populasi, setiap iterasi, populasinya kita gandakan, lalu kita pangkas dan ambil setengahnya yang paling baik (untuk menentukan mana yang lebih baik, digunakan suatu ukurang yang disebut "fitness factor").
Pada masalah ini, populasinya adalah graph, dan fitnes factornya adalah nilai M dari graph tersebut. Jadi apabila paragraf diatas diterjemahkan, kurang lebih algonya: simpen set yang berisi banyak graph, dalam setiap iterasi kita coba buat graph-graph baru dari graph yang sudah ada, hitung nilai M dari semua graph, dan pilih setengah yang paling baik.
Jadi logikanya, dalam setiap iterasi (atau bisa disebut "generasi"), graph-graph yang kita punya pasti tidak lebih jelek dari graph sebelum iterasi tersebut.
Sekarang, gimana caranya menggandakan graph? Ada dua cara:
-Crossover: pilih dua graph di set tersebut, tuker-tuker nilai pada edge-edge, dan jadikan graph hasilnya sebagai "anak" dari dua graph tersebut dan masukkan ke set. Kalau aku, aku tentukan suatu peluang, dimana peluang tersebut menyatakan berapa kemungkinan suatu edge ditukar dengan edge lain.
-Mutation: pilih sebuah graph di set tersebut, cari sebuah edge yang menyebabkan dua buah path memiliki sum yang sama, dan ganti nilai di edge tersebut menjadi suatu angka random dan masukkan graph tersebut kedalam set. Untuk mencari edge yang memenuhi kriteria dengan cepat, bisa dilakukan dengan mensimulasikan pencarian nilai M, namun apabila ketemu suatu path yang dimana sumnya sudah pernah didapat sebelumnya, masukkan semua edge yang ada di path ini kedalam jawaban.
Kesuksesan algoritma ini juga bergantung kepada "keteracakan" graph yang kita buat. Berikut adalah beberapa tips:
-Jangan sampai ada graph duplikat dalam set:
Jangan sampai suatu operasi crossover atau mutation menghasilkan suatu graph yang sama. Untuk mengatasinya, bisa di cek graph hasil mutasi/crossovernya apakah sama seperti orang tuanya, apabila sama, maka ulangi saja proses crossover/mutasinya.
-Mutasi dan crossover adalah operasi yang sama-sama penting:
Sekilas, mutation kelihatan seperti operasi yang lebih penting dikarenakan dia "memperbaiki" edge yang sudah pasti salah. Namun, terkadang tukarannya crossover sangat sakti dan bisa menghasilakn graph dengan nilai M +2 atau +3 dari induknya! dimana mutation paling banyak bisa menghasilkan graph dengan M +1 dari induknya.
-Graph hasil crossover memiliki peluang untuk mengalami mutasi
More random, more better.
-Tambahkan "priority"
Terkadang, populasinya bisa remis dan bakal nyangkut "itu-itu aja" selama beberapa generasi. Caranya mengakali adalah menambahkan variabel baru kedalam masing-masing individu, yaitu priority. Jadi, ketika kita melakukan "seleksi alam", kita memilih graph graph dengan nilai M yang lebih baik, namun apabila dua graph memiliki nilai M yang sama, kita memprioritaskan graph yang memiliki nilai M lebih tinggi. Jadi dijamin populasi setiap iterasi bakal lebih "fresh". Bahkan, priority dalam populasi tersebut bisa di berikan ulang setelah beberapa generasi karena ini adalah operasi yang ringan. Pemberian priority bisa dilakukan dengan cukup memberikan bilangan random.
bagaimana dengan ukuran populasi ideal? Semakin tinggi ukuran populasi kita, maka semakin cepat ditemukan jawabannya, namun tentunya komputasinya (dalam hal ini, yang berat adalah mencari nilai M) akan semakin berat. Untuk N=8, aku menggunakan ukuran populasi=80 dan mendapat jawaban fullnya dalam kurang dari 10 menit, namun untuk N yang lebih tinggi, ukuran populasinya harus disesuaikan agar tidak terlalu lambat.
Terakhir, masalah mendapatkan poin di soal ini. Walaupun cara ini bisa mendapatkan solusi full untuk subtask 7 dan 8 dengan waktu yang masuk akal (2 jam untuk subtask 7, 3 setengah jam untuk subtask 8), solusi ini bekerja super cepat apabila digunakan untuk nyampah. Contohnya, apabila target kita adalah 3/2L untuk subtask 8 (17 dari 25 poin), dengan ukuran populasi yang baik, solusi bisa didapat dalam 20 generasi (sangat cepat :O). Bahkan untuk nilai yang sangat dekat dengan L, misal aku coba 22/20L untuk subtask 7, pencarian yang membutuhkan dua jam untuk solusi fullnya tiba-tiba hanya membutuhkan beberapa menit. Dan itu sudah 15 dari 17 poin yang didapat. Aku malas nyoba nilai-nilai L yang lain karena gaada faedahnya, dan lebih bagus apabila pembaca blog ini yang mencoba sendiri. Aku juga tidak menulis berapa populasi ideal untuk masing-masing subtask, karena salah satu serunya dari genetics algorithm ini adalah mengira-ngiranya (ingat, semakin tinggi populasi, semakin sedikit generasi yang dibutuhkan, tapi komputasi per generasi jadi semakin banyak).
Jadi, solusi ini sangat cocok digunakan untuk mencari parsial pada subtask ini. oh, kecuali subtask 6, itu 10 menit dapet kok solusinya :). Tentunya, aku harus mengACkan soal ini makanya aku niat nungguin 5 jam untuk solusi subtask 7 dan 8, namun apabila soal tipe ini muncul lagi di OSN dan algo serupa bisa digunakan, jangan takut untuk mencari poin parsial, aku rasa 90+ poin dalam setengah jam mengenerate solusi sangat mungkin.
Untuk alasan yang jelas, temen-temen pelatnasku terkadang bilang algo ini sebagai Thanos theorem...
Penutup
Sekian pembahasan OSN 2016 dari aku, semoga bisa dipakai sebagai persiapan menuju OSN yang tinggal sebulan lagi. Aku sadar bahwa pembahasan ini masih jauh dari kata sempurna. Apabila ada kesalahan (atau keberatan) bisa langsung hubungi aku :).
Catatan:
Aku engga ngeshare source codeku, karena implementasi itu bagian serunya. Tapi bakal ada beberapa pseudocode, aku tulis menggunakan bahasa pseudopascal :v.
Day 1
Pasar 16 Ilir
Subtask 1-6,8 (67 poin)
Perhatikan bahwa N*M paling banyak 20, cukup kecil jadi kita bisa buat semua kemungkinan jalannya. Kita asumsikan kasus terburuk, yaitu N*M=20. ini akan maksimum ketika R=4 dan C=5 (atau sebaliknya). Jadi banyaknya kemungkinan jalan cukup sedikit. Kita bisa simpan semua kemungkinan jawabannya dalam array, dan apabila ditanya harga antar P dan Q tinggal iterasi saja isi arraynya.
Nah, sekarang tinggal gimana caranya generate semua kemungkinan? pake teknik backtracking. Jadi kamu mulai dari titik (0,0), simpen array global yang nandain petak udah divisit atau belum, lalu coba visit. apabila udah sampai titik (n,m), masukin total sum sekarang ke array jawaban. Kurang lebih pseudocodenya kaya gini:
visited <- array boolean berukuran 36 x 36
value <- array berukuran 36x36, nilai dari matriks
sum <- sebuah integer
nilai <- sebuah array yang menampung harga-harga yang mungkin.
function backtrack(x,y : integer)
begin
if(visited(x,y)=FALSE)
begin
visited(x,y):=true;
sum:=sum+value(x,y);
if((x=N)AND (y=M)) //masukin sum ke dalam array nilai
else begin
backtrack(x+1,y);
backtrack(x,y+1);
backtrack(x-1,y);
backtrack(x,y-1);
end;
sum:=sum-value(x,y);
visited(x,y)=false;
end;
end;
Subtask 1-8 (100 poin)
Masalah dari algoritma sebelumnya adalah pencarian nilai diantara P dan Q bisa O(logn).
Kalau misal array nilai kita sudah sorted, kita bisa mencari banyaknya elemen diantara P dan Q dalam log n menggunakan binary search. Jadi, setelah mendapatkan array jawaban dengan backtracking, arraynya di sort dengan algo sorting nlogn lalu dijawab menggunakan binary search.
Taming a Bomb
Subtask dengan Bomb tipe-0 (37 poin)
Kita bisa coba tekan 1 sampai N secara berurutan, lalu N sampai 1 secara berurutan. lalu, selama belum terdengar "BIP" dua kali, tekan tombol acak. Jadi kurang lebih penekanan tombol kita kelihatan seperti ini:
1 2 3 4 5 ... N
N N-1 N-2 ... 3 2 1
X X X X X (untuk suatu X acak).
Kita juga mencatat kapan terdengar BIP pertama (sebut T1) dan BIP kedua (sebut T2). misal juga tombol targetnya adalah A, dan delaynya T.
Pada baris pertama, tombol bernomor i akan ditekan pada waktu ke-i. didapat persamaan A + T = T1.
Pada baris kedua, tombol bernomor i akan ditekan pada waktu ke-2N-i+1. didapat persamaan 2N-A+1+T=T2 -> T-A = T2-2N-1.
karena dua persamaan tersebut memiliki ruas kanan konstanta, jadi dua persamaan tersebut merupakan sistem persamaan dua variabel. Diselesaikan didapat A = (T1-T2+2N+1)/2. Berikutnya tinggal dipencet terus A sampai berhasil :).
Algo ini memerlukan 3N pemencetan dalam kasus terburuk untuk mendapat 2 BIP, ditambah kasus terburuk 2N pemencetan setelah nilai A ketemu. total dibutuhkan paling banyak ~5N pemencetan.
Subtask dengan bomb tipe-0 dan tipe-1 (100 poin)
Masalah pada algo sebelumnya adalah apabila bombnya tipe 1 dimana nilai A dan Knya kecil. misal A=1 dan K=1. maka menggunakan algo sebelumnya bomb akan keburu meledak sebelum BIP kedua terdengar.
Salah satu solusi yang mungkin menggunakan algoritma diatas adalah menanyakan permutasi 1-N secara acak dan pada giliran berikutnya menanyakan kebalikan dari permutasi tersebut. Sebagai contoh apabila n=7, kamu bisa nyoba nanya
7 3 2 4 3 1
1 3 4 2 3 7
X X X X X X (untuk suatu X acak)
persamaannya tinggal dimodif dikit, disini A=(T1-T2+2N+1)/2 maksudnya bukan berarti tombol jawabannya adalah A, melainkan A=tombol ke-i dalam permutasi tersebut. Jadi misal didapat A=3 menggunakan permutasi diatas, maka tombol jawabannya adalah 2.
Memang, solusi ini tetap bisa gagal, tapi peluangnya kecil dan layak dicoba apabila merasa beruntung :)
Kalau kamu orangnya ga percaya keajaiban kaya aku, tenang, ada solusi pastinya kok:
Jadi masalahnya adalah jaraknnya yang kepanjangan apabila nilai Knya kecil. Jadi kenapa ga kita bagi dua aja arraynya? misal kita coba solve 1..N/2 dan N/2..N secara terpisah (asumsi N genap, apabila ganjil, jadikan genap dan apabila ga ketemu jawabannya maka jawabannya bilangan yang ga kepilih).
Jadi kita pertama cari tau apakah jawabannya ada di antara 1..N/2.
kita tanya
1 2 3 ... N/2
N/2 N/2-1 ... 3 2 1
X X X X (untuk suatu X acak)
Yay, dengan begini, bomb tidak akan meledak karena pasti dua buah BIP berjarak tidak lebih dari N :D. Karena BIP pertama pasti muncul setelah minimal 3N/2 penekanan, kita bisa pruning apabila setelah 3N/2 penekanan BIP belum juga terdengar, maka jawabannya bukan pada range ini.
tunggu dulu... worst case pertanyaanya apabila Knya gede, didapat banyaknya pertanyaan 3N/2 + 3N/2 untuk bertanya dua range, ditambah 2N (asumsi K=N-1) untuk menjawab apabila tombol sudah ketemu. Jadi total pertanyaannya 7N dan tidak akan lolos subtask terakhir.
OH KALAU GITU DIBAGI 3 AJA RANGENYA, COBA TANYA 1..N/3 ,N/3+1..2N/3, 2N/3+1..N.
-orang yang bilang ternary search lebih cepet dari binary search.
hmm, tadi kalau ga dibagi, butuh 4N pertanyaan, dibagi dua butuh 6N, jadi kalau dibagi 3, bakal naik dong :(.
Balik ke bagi dua tadi, ternyata kita cuman perlu optimisasi N pertanyaan. Ternyata optimisasinya bertanyanya cukup digabung aja. jadi tanyanya
1 2 3 ... N/2
N/2 N/2-1 ... 3 2 1
N/2+1 N/2+2 ... N
N N/2-1 ... 1
X X X X X
worst case banyaknya pertanyaan, untuk mencari tombol dibutuhkan 3N, ditambah untuk jawab 2N, jadi pas 5N :) (sebenernya kurang dikit sih... soalnya aku banyak estimasi).
Pos Wisata Sungai
Subtask 1-9 (100 poin)
Ada properti operasi XOR sebagai berikut: Apabila kita punya suatu bilangan biner A, hanya ada tepat 1 bilangan B dimana A xor B = C.
Maka dari itu, Seandainya kita sudah menentukan nilai W1,W2,...W(n-1) dan bilangan biner yang kita dapat adalah A, kita harus memilih Wn sedemikian rupa sehingga A XOR Wn memiliki K buah bit 1. Dengan kombinasi didapat banyaknya bilangan biner dengan N digit dan K buah bit 1 adalah C(M,k). menggunakan properti XOR diatas, untuk setiap bilangan biner yang mungkin jadi jawaban, hanya ada 1 buah Wn yang memenuhi A XOR Wn = bilangan tersebut. Jadi banyaknya Wn yang memenuhi ada sebanyak C(M,k) pula.
Nah sekarang tinggal W1 sampai W(n-1) secara sembarang. Ini sama dengan mencari banyaknya bilangan biner M digit yang mungkin, yaitu 2^M. Karena ada (n-1) bilangan, maka totalnya ada (2^M)^(N-1) kemungkinan. rumus akhirnya menjadi 2^(M*(N-1)) * C(M,K).
Masalah yang mungkin muncul adalah gimana caranya menghitung C(M,K) modulo 10^9+7, karena ada pecahan faktorial. Perlu diketahui bahwa 1/n mod P = n^(P-2) mod P untuk suatu P bilangan prima (fermat's little theorem). solusinya adalah semua inverse factorial dan factorial bisa di precomputasi dengan O(N) dengan cara berikut:
f <- f[i] = nilai dari i! mod 10^9+7
inv <- inv[i] = nilai dari 1/i! mod 10^9+7
for i :=1 to 1000000 do
begin
f[i]:=f[i-1]*i mod 10^9+7;
inv[i]=inv[i-1]*(i ^ (10^9+5)) mod 10^9+7;
end;
untuk operasi pemangkatan, bisa gunakan pemangkatan DNC log(n).
Untuk soal ini, aku mohon maaf karena langsung solusi AC, aku udah coba-coba cari solusi non ac untuk subtask yang lebih kecil, namun selalu saja observasinya trivial dan mudah ditingkatkan agar jadi solusi AC :"
DAY 2
Robot Pempek
Subtask 1-5 (59 poin)
Misalkan D(A,B) menyatakan jarak manhattan dari titik A ke titik B. Kita juga nomori tempat pemancingannya dengan nomor 1 sampai N.
Misal pergerakan robot adalah C1,C2,C3,...,CM, dimana Ci menyatakan suatu titik pemancingan. Jelas bahwa D(C1,C2) > D(C2,C3) > D(C3,C4) > ... > D(C(M-1),CM).
Apabila semua tempat pemancingan kita jadikan vertex dalam suatu directed graph, dimana edge yang menghubungkan vertex i ke vertex j menyatakan bahwa apabila robot berada di vertex i maka pergerakan selanjutnya adalah ke vertex j. Jelas bahwa banyaknya edge yang keluar dari suatu vertex maksimal 1.
Sebuah cycle dengan panjang N didefinisikan sebagai serentetan vertex {V1,V2,V3,...,VN} dimana ada edge yang menghubungkan Vi dan V(i+1) untuk 1<=i<N dan VN dan V1.
Observasi: panjang cycle maksimum dari graph yang terbentuk maksimal 2.
Bukti:
misal ada cycle dengan panjang lebih dari 2. misal cycle tersebut sepanjang N dengan vertex {V1,V2,V3,...,VN}. Karena ada edge dari VN ke V1, maka D(V1,VN) < D(V(N-1),VN). Dari observasi pergerakan robot, didapat D(V1,V2) > D(V(N-1),VN). Maka setelah mensubstitusi D(V(N-1),VN) pada kedua persamaan, didapat D(V1,V2) > D(V1,VN). ini artinya apabila robot ada di V1, dia akan lebih memilih ke VN daripada ke V2. Sebuah kontradiksi. (terbukti).
Jadi graphnya kurang lebih berbentuk seperti ini:
 |
| maksudnya panah dua arah itu, dari 3 nxtnya 4, dan dari 4 nxtnya 3. |
Jadi, pertama kita precompute tempat pemancingan terdekat untuk setiap tempat pemancingan (looping aja, O(K^2)) misal nxt[i] adalah indeks tempat pemancingan yang berikutnya bakal divisit robot apabila robot berada pada tempat pemancingan ke-i atau bernilai -1 apabila ada lebih dari dua tempat pemancingan dengan jarak sama dari tempat pemancingan ke-i. Lalu bisa diaplikasikan dynamic programming.
dp[pos][last] -> tempat berhentinya robot, apabila robot berada pada tempat pemancingan ke-pos dengan tempat pemancingan terakhir yang dikunjungi robot adalah tempat pemancingan ke-last.
Transisi:
dp[pos][last] = pos (apabila nxt[i]=-1 atau nxt[i]=pos)
dp[pos][last] = dp[nxt[pos]][pos] (apabila tidak)
DP ini bekerjan dalam O(K^2). Untuk setiap query, cukup cari tempat pemancingan terdekat dari query tersebut dengan iterasi O(K). Total kompleksitas solusi: O(K^2 + QK).
Subtask 1-6 (76 poin)
Kendalanya adalah pada subtask ini, Q bisa mencapai 300000. Jadi pada saat menjawab query, kita bakal TLE saat mencari tempat pemancingan terdekatnya. Jadi dalam mencari tempat pemancingan terdekatnya, harus dilakukan optimisasi.
Optimisasinya adalah melakukan BFS Pararel dari setiap tempat pemancingan. Yakni, kita push semua tempat pemancingan kedalam queue secara bersamaan, lalu tandai suatu petak sebagai visited dengan tempat pemancingan terdekatnya adalah tempat pemancingan yang sedang di proses. Apabila ternyata sebuah titik memiliki dua atau lebih tempat pemancingan terdekat dengan jarak sama, tandai tempat tersebut dengan -1.
Ini bisa TLE karena setiap titik berpotensi divisit lebih dari sekali (bisa K kali!) jadi caraku mengatasinya adalah melakukan deepening bfs secara manual. Yakni, selama jarak yang dalam front queuenya sama, di proses saja, namun state selanjutnya tidak langsung di push kembali kedalam queue tersebut, melainkan ke sebuah stack. Nanti, ketika semua state dengan jarak X telah diproses, baru dipindahkan seluruh isi stack kedalam queue, namun, apabila suatu titik sudah dimasukkan kedalam queue dan masih ada state dengan titik itu lagi di dalam stack, maka titik kedua itu di ignore. Karena state dengan suatu titik yang mengandung nilai -1 pasti dimasukkan lebih akhir (artinya bakal masuk lebih awal ke queue, ingat stack LIFO), maka dijamin bahwa state itulah yang masuk kedalam queue. Dengan itu, kita menjamin bahwa setiap titik akan divisit tepat sekali, dan total prekomputasi jarak terdekat untuk setiap titik yang bukan tempat pemancingan berjalan dalam O(NM).
Untuk query, apabila yang di query tempat non pemancingan, bisa gunakan hasil precomputasi diatas, apabila tidak cukup jalankan seperti subtask sebelumnnya. DP masih sama seperti sebelumnya. Kompleksitas solusi (O(K^2 (DP,precompute nxt[i]) + MN (precompute non tempat pemancingan)).
Subtask 1-7 (100 poin)
Optimisasi terakhir yang perlu dilakukan agar solusinya accepted adalah precompute tempat pemancingan terdekat dari suatu tempat pemancingan. Kita tidak bisa menggunakan BFS pararrel karena bfs harus "menembus" titik yang sudah visited.
Ternyata, solusinya adalah cukup BFS biasa dari setiap tempat pemancingan, apabila ketemu sebuah tempat pemancingan lain, maka break dan tandai tempat pemancingan tersebut sebagai terdekat. Apabila ada lebih dengan jarak sama, maka tandai tempat itu sebagai -1.
Ini enggak bakal TLE, karena logikanya semakin banyak tempat pemancingannya, BFS akan semakin cepat selesai dan worst casenya adalah apabila ada dua buah tempat pemancingan, satu di pojok kiri bawah, dan satu di pojok kanan atas. Jadi kompleksitas total dari K BFS ini adalah O(MN).
DP kita juga harus dimodifikasi.
DP[i] -> tempat pemancingan terakhir, apabila robot berada di tempat pemancingan ke-i.
Ingat kembali bahwa graph tersebut memiliki panjang cycle maksimal dua, maka kita cek apakah posisi sekarang merupakan suatu cycle. Apabila tidak, maka dijamin kita akan bergerak lurus dan tidak akan pernah melewati titik-titik yang sudah pernah dilewati sebelumnya. kurang lebih seperti ini:
DP[i] = i (apabila nxt[i]=-1)
DP[i] = nxt[i] (apabila nxt[nxt[i]]=i)
DP[i] = DP[nxt[i]] (else)
Jadi total kompleksitas DPnya pun jadi O(K) doang.
Total kompleksitas : O(MN + K)
Belanja Suvenir
Subtask 1-5 (54 poin)
Perhatikan bahwa apabila ada solusi dengan M=X, maka pasti ada solusi dengan M=i (dimana i<X), dan apabila tidak ada solusi dengan M=X, maka pasti tidak ada solusi dengan M=i (dimana i>X). Jadi, kita bisa binary search jawabannya. Yakni, set sebuah lowerbound dan upperbound. lalu cari midnya. Apabila ada solusi untuk M=mid, maka pasti ada solusi untuk <mid, jadi lowerboundnya kita naikkan jadi mid. Apabila tidak, maka upperboundnya kita turunkan jadi mid-1. Pseudocode
left:=1,right:=2000000;
while(left<right)
begin
mid:=(left+right)/2;
if(ada solusi untuk M=mid) left:=mid;
else right:=mid-1
end;
//jawaban = left;
Nah sekarang tinggal gimana caranya ngecek apakah ada jawaban untuk M=mid. caranya adalah cukup coba semua kemungkinan mulai belanjannya kwik dan kwak, yakni misal kwik mulai belanja pada toko ke-i, dan kwak pada toko ke-j. Apabila semua suvernir berbeda, maka valid. Untuk ngeprint jawaban apabila ada jawaban dapat dilakukan dengan cara serupa. Kompleksitas untuk sekali cek adalah O(n^3). karena binary search, ditambah O(logn). total kompleksitasnya O(n^3 log n).
Subtask 1-7 (100 poin)
Mengecek valid untuk suatu M dapat dipercepat. dengan teknik sliding window. Jadi, kita coba apakah segmen [1,M],[2,M+1],[3,M+2],... bisa menjadi jawaban secara beruntun. Untuk mengecek apakah suatu segmen [X,Y] bisa menjadi jawaban, kita buat array freq[] dimana freq[i] menyatakan frekuensi banyaknya elemen pada segment tersebut. Jawaban valid apabila untuk semua i, freq[i]<=1.
Kita bisa masukkan semua nilai di segmen [1,M] kedalam array. Lalu perhatikan ketika kita mau cek segment [2,M+1], kita tidak perlu membuat array freq[] dari awal. Cukup "hapus" elemen ke-1 dari freq, dan "tambahkan" elemen ke-(M+1) ke freq. Jadi kita bisa cek apakah sebuah segment selanjutnya valid dalam O(1). Untuk mengecek apakah untuk semua i, freq[i]<=1, cukup maintain sebuah variabel yang menyatakan banyaknya elemen dalam freq[i] yang >1, dan update sejalan dengan array freq[]. Kompleksitasnya O(n log n).
Wisata Palembang
ini dia :) menurutku ini soal keren dan aku bangga bisa jadi orang kedua di Indonesia dan ketiga dunia yang bisa mensolve problem ini dengan fullscore :D.
Subtask 1-5 (43 poin)
Untuk soal ini, diperlukan suatu konsep yaitu "randomization". Jadi, untuk mensolve subtask ini, kita perlu menggenerate random graph, lalu mengecek apakah memenuhi kriterianya dan apabila tidak, coba generate baru lagi sampai ketemu. Setiap bahasa pasti mempunyai suatu library yang generate random numbers (rand() kalau C++, random kalau pascal). Pseudocode generate random graph
a <- sebuah array dua dimensi yang dimana a(i,j) nyimpen nilai dari panjang jalan (i,j)
for i :=1 to n
for j:=i+1 to n
a(i,j) := a(j,i) := random(L); //milih 1 bilangan acak dengan jangkauan 1 sampai L.
Lalu cek apakah graphnya valid dengan cara bruteforce (n!). apabila tidak, ulangi lagi. (looping while(true)).
Solusi ini akan mengenerate jawaban untuk subtask 1 sampai 5 dengan cukup cepat (hampir instan).
Karena ini solusi output only, jadi jawaban pada subsoal ini dapat disimpan, dan penghitungan nilai pada subsoal berikutnya dilakukan secara terpisah :).
Subtask 6-8 (0-57 poin, tergantung kesabaran)
Berapa banyak jalan berbeda maksimal yang dapat kita bentuk apabila kita punya N lokasi (termasuk hotel?). Jawabannya adalah (N-1)!/2. Karena hotel (lokasi ke 0) selalu berada di awal dan akhir wisata. dan (N-1) sisanya bebas dikunjungi dengan urutan apapun. Tapi dikarenakan pengunjungan simetris (i.e, ngunjungin 1-2-3 pasti memiliki sum sama dengan 3-2-1) maka banyaknya sum berbeda maksimal kita bagi 2 dan didapat (N-1)!/2.
Nah apabila kita perhatikan nilai M yang diminta pada 3 subtask terakhir ini, nilai M = (N-1)!/2 :O. Jadi diminta nilai sum yang tepat sama dengan jumlah maksimal yang dapat dibentuk. Algo random diatas memiliki peluang yang terlampau kecil untuk bisa mendapatkan jawaban, tahun lalu aku sudah coba seharian jalanin dan tidak ketemu jawabannya. Jadi, yang kita butuhkan adalah algo yang lebih baik dalam mencari jawabannya.
Masalah dari algo random diatas adalah, dia tidak peduli seberapa dekatnya kita terhadap jawaban, hanyalah bahwa jawabannya ketemu atau tidak. Contohnya, ambil testcase dimana M=2520. Algo random tersebut mungkin saja beberapa kali menemukan graph dengan M=2518 atau 2519, tapi tetap saja tidak bakal dihiraukan apabila jawabannya tidak tepat M=2520. Jadi? kenapa engga kita "membangun" solusi optimalnya dari solusi-solusi yang sudah ada?
Memperkenalkan : Genetics algorithm
intinya, kita menyimpan suatu populasi, setiap iterasi, populasinya kita gandakan, lalu kita pangkas dan ambil setengahnya yang paling baik (untuk menentukan mana yang lebih baik, digunakan suatu ukurang yang disebut "fitness factor").
Pada masalah ini, populasinya adalah graph, dan fitnes factornya adalah nilai M dari graph tersebut. Jadi apabila paragraf diatas diterjemahkan, kurang lebih algonya: simpen set yang berisi banyak graph, dalam setiap iterasi kita coba buat graph-graph baru dari graph yang sudah ada, hitung nilai M dari semua graph, dan pilih setengah yang paling baik.
Jadi logikanya, dalam setiap iterasi (atau bisa disebut "generasi"), graph-graph yang kita punya pasti tidak lebih jelek dari graph sebelum iterasi tersebut.
Sekarang, gimana caranya menggandakan graph? Ada dua cara:
-Crossover: pilih dua graph di set tersebut, tuker-tuker nilai pada edge-edge, dan jadikan graph hasilnya sebagai "anak" dari dua graph tersebut dan masukkan ke set. Kalau aku, aku tentukan suatu peluang, dimana peluang tersebut menyatakan berapa kemungkinan suatu edge ditukar dengan edge lain.
-Mutation: pilih sebuah graph di set tersebut, cari sebuah edge yang menyebabkan dua buah path memiliki sum yang sama, dan ganti nilai di edge tersebut menjadi suatu angka random dan masukkan graph tersebut kedalam set. Untuk mencari edge yang memenuhi kriteria dengan cepat, bisa dilakukan dengan mensimulasikan pencarian nilai M, namun apabila ketemu suatu path yang dimana sumnya sudah pernah didapat sebelumnya, masukkan semua edge yang ada di path ini kedalam jawaban.
-Jangan sampai ada graph duplikat dalam set:
Jangan sampai suatu operasi crossover atau mutation menghasilkan suatu graph yang sama. Untuk mengatasinya, bisa di cek graph hasil mutasi/crossovernya apakah sama seperti orang tuanya, apabila sama, maka ulangi saja proses crossover/mutasinya.
-Mutasi dan crossover adalah operasi yang sama-sama penting:
Sekilas, mutation kelihatan seperti operasi yang lebih penting dikarenakan dia "memperbaiki" edge yang sudah pasti salah. Namun, terkadang tukarannya crossover sangat sakti dan bisa menghasilakn graph dengan nilai M +2 atau +3 dari induknya! dimana mutation paling banyak bisa menghasilkan graph dengan M +1 dari induknya.
-Graph hasil crossover memiliki peluang untuk mengalami mutasi
More random, more better.
-Tambahkan "priority"
Terkadang, populasinya bisa remis dan bakal nyangkut "itu-itu aja" selama beberapa generasi. Caranya mengakali adalah menambahkan variabel baru kedalam masing-masing individu, yaitu priority. Jadi, ketika kita melakukan "seleksi alam", kita memilih graph graph dengan nilai M yang lebih baik, namun apabila dua graph memiliki nilai M yang sama, kita memprioritaskan graph yang memiliki nilai M lebih tinggi. Jadi dijamin populasi setiap iterasi bakal lebih "fresh". Bahkan, priority dalam populasi tersebut bisa di berikan ulang setelah beberapa generasi karena ini adalah operasi yang ringan. Pemberian priority bisa dilakukan dengan cukup memberikan bilangan random.
bagaimana dengan ukuran populasi ideal? Semakin tinggi ukuran populasi kita, maka semakin cepat ditemukan jawabannya, namun tentunya komputasinya (dalam hal ini, yang berat adalah mencari nilai M) akan semakin berat. Untuk N=8, aku menggunakan ukuran populasi=80 dan mendapat jawaban fullnya dalam kurang dari 10 menit, namun untuk N yang lebih tinggi, ukuran populasinya harus disesuaikan agar tidak terlalu lambat.
Terakhir, masalah mendapatkan poin di soal ini. Walaupun cara ini bisa mendapatkan solusi full untuk subtask 7 dan 8 dengan waktu yang masuk akal (2 jam untuk subtask 7, 3 setengah jam untuk subtask 8), solusi ini bekerja super cepat apabila digunakan untuk nyampah. Contohnya, apabila target kita adalah 3/2L untuk subtask 8 (17 dari 25 poin), dengan ukuran populasi yang baik, solusi bisa didapat dalam 20 generasi (sangat cepat :O). Bahkan untuk nilai yang sangat dekat dengan L, misal aku coba 22/20L untuk subtask 7, pencarian yang membutuhkan dua jam untuk solusi fullnya tiba-tiba hanya membutuhkan beberapa menit. Dan itu sudah 15 dari 17 poin yang didapat. Aku malas nyoba nilai-nilai L yang lain karena gaada faedahnya, dan lebih bagus apabila pembaca blog ini yang mencoba sendiri. Aku juga tidak menulis berapa populasi ideal untuk masing-masing subtask, karena salah satu serunya dari genetics algorithm ini adalah mengira-ngiranya (ingat, semakin tinggi populasi, semakin sedikit generasi yang dibutuhkan, tapi komputasi per generasi jadi semakin banyak).
Jadi, solusi ini sangat cocok digunakan untuk mencari parsial pada subtask ini. oh, kecuali subtask 6, itu 10 menit dapet kok solusinya :). Tentunya, aku harus mengACkan soal ini makanya aku niat nungguin 5 jam untuk solusi subtask 7 dan 8, namun apabila soal tipe ini muncul lagi di OSN dan algo serupa bisa digunakan, jangan takut untuk mencari poin parsial, aku rasa 90+ poin dalam setengah jam mengenerate solusi sangat mungkin.
Untuk alasan yang jelas, temen-temen pelatnasku terkadang bilang algo ini sebagai Thanos theorem...
Penutup
Sekian pembahasan OSN 2016 dari aku, semoga bisa dipakai sebagai persiapan menuju OSN yang tinggal sebulan lagi. Aku sadar bahwa pembahasan ini masih jauh dari kata sempurna. Apabila ada kesalahan (atau keberatan) bisa langsung hubungi aku :).
Comments
Post a Comment