Jun 022011
 

Minggu, 29 Mei 2011 yang lalu barusan Jollymoo 11 berlalu. Tingkat kesulitan Jollymoo 11 adalah normal (bukan untuk divisi 2 seperti Jollymoo 10), jadi ada beberapa soal yang cukup menantang. Di sini gw mau bahas soal-soalnya, dan semoga bisa ngasi sedikit pencerahan buat yang ga bisa. Anyway, karena ini bukan kontes untuk divisi 2, maka beberapa penjelasan gw akan singkat banget, karena gw anggap trivial dan lu orang (harusnya) bisa.

Soal-soal Jollymoo 11 bisa dilihat di SINI.

Soal-soal kontes ini beberapa diambil dari arsip kontes-kontes lama (SRM, Codeforces, dll) yang diubah dan disiapkan, jadi gw ga ngambil credits apapun untuk soal-soal yang ada.

A. Po Memungut Bola
Mula-mula formulasikan dulu soal ini ke dalam bentuk:

f(S) = i=1..N, j=1..N, i and j not in S min{ f(S U i U j) + cost[0][i] + cost[i][j] + cost[j][0] }

S: himpunan yang berisi bola-bola yang sudah dikumpulkan.
f(S): jarak minimum yang diperlukan untuk mengumpulkan semua bola yang tidak ada di dalam himpunan S.
U: union, gabungan.
cost[a][b]: jarak dari a ke b.
0: posisi awal Po.

Perhatikan bahwa i bisa sama dengan j, yang artinya hanya 1 bola yang diambil. Tentunya himpunan di atas bisa direpresentasikan ke dalam bitmask karena N maksimal hanya 20, sehingga formula di atas bisa kita implementasikan ke dalam dynamic programming. Berapa kompleksitasnya? Ada sebanyak 2N state dan untuk menghitung sebuah state diperlukan iterasi N2 sehingga total kompleksitas waktunya adalah O(N2 . 2N). Solusi ini masih TLE.

Solusi di atas bisa kita optimisasi dengan ide seperti ini: Seandainya terdapat 4 bola: a, b, c dan d; urutan pengambilan a-b dan c-d (ambil a dan b, kemudian ambil c dan d) akan menghasilkan total jarak yang sama dengan urutan c-d dan a-b. Dengan ide ini, kita bisa menghilangkan salah satu iterasi (i) dan cukup melakukan iterasi pada j (pilih satu bola sembarang dan iterasi pasangannya). Dengan demikian total kompleksitas yang diperlukan menjadi O(N . 2N).

Note: hanya perlu menambahkan satu line “break;” di solusi yang O(N2 . 2N).

B. Bilangan K-Prima
Ada beberapa yang menyelesaikan soal B dengan bar-bar, iterasi dari 1..N dan cari ada berapa bilangan yang k-prima. Setiap bilangan diuji k-primanya dengan iterasi akar n. Solusi ini cukup ok, tapi karena time-limitnya hanya 1 detik, solusi ini pasti dapat TLE (tanpa optimasi).

Pertama, hitung dulu (precompute) faktor bilangan prima terbesar dari setiap bilangan dari 1..MAXN (100.000). Ini bisa dilakukan dengan modifikasi algoritma sieve.

int f[100005] = {0};
for ( int i = 2; i <= maxn; i++ ) {
  if ( f[i] == 0 ) {
    for ( int j = i; j <= maxn; j += i ) {
      f[j] = i;
    }
  }
}

Code di atas ada iterasi dua tingkat tapi kompleksitasnya bukan O(N2), tapi hanya O(N lg N). Mengapa? ada hubungannya dengan harmonic series.

Berikutnya, untuk setiap query tinggal looping dari 1..N dan hitung ada berapa bilangan yang memenuhi k-prima.

C. Gaji Perusahaan
Rasanya soal ini nggak susah, tinggal DP sederhana aja.

D. Putar dan Berputar
Soal ini bisa diartikan begini: diberikan sebuah directed graph dimana setiap node hanya memiliki sebuah out-degree, cari path terpanjang yang tidak melewati edge yang sama dua kali.

Tentunya graph tersebut bisa memiliki cycle, jadi kita terlebih dahulu harus mencari semua cycle yang ada pada graph tersebut. Jika semua cycle sudah didapatkan, sisanya mudah.

E. Himpunan Bilangan Pembagi
Soal ini juga nggak susah, ada banyak approach yang bisa dipakai buat menyelesaikan soal ini, salah satunya adalah DP. Bisa juga diselesaikan dengan menghitung jumlah faktor prima dari N.

Contoh, 72 = 23 * 32, sehingga total ada (3 + 2) + 1 bilangan yang lebih kecil dari N yang habis membagi N dan bilangan itu juga habis dibagi bilangan yang lebih kecil.

72 = 23 * 32
24 = 23 * 31
8 = 23 * 30
4 = 22 * 30
2 = 21 * 30
1 = 20 * 30

EDIT: Yang terakhir seharusnya 20 * 30, tadinya 20 * 32. Thanks to William.

F. Interval
Hanya ada 4 jenis output yang mungkin, yaitu:

  • Tidak ada interval yang overlap, jika demikian output semua interval.
  • Tidak ada interval yang demikian, output -1.
  • Ada satu interval yang demikian.
  • Ada dua interval yang demikian.

Keempat kemungkinan output tersebut sudah diberikan di contoh input, jadi seharusnya tidak ada yang terkena “tricky case” di soal ini.

Untuk menyelesaikan soal ini, kita perlu mengetahui berapa interval yang bisa diambil maksimal sedemikan sehingga tidak ada interval yang saling overlap. Jika kita mengetahui ini, maka interval yang tidak diambil itu adalah interval yang akan menyebabkan overlap.

Mula-mula urutkan data interval yang ada berdasarkan R (end) secara menaik, dan ambil interval satu per satu namun interval tersebut tidak boleh overlap dengan interval-interval yang sudah diambil. Mirip dengan interval selection problem kan?

Jika dari proses di atas didapatkan tidak ada interval yang tidak diambil, maka output semua interval. Jika ada dua atau lebih interval yang tidak diambil, maka output -1. Jika hanya ada satu interval yang tidak diambil, kita harus memeriksa bagaimana interval ini overlap dengan interval yang lain. Jika interval ini hanya overlap dengan satu interval lain, maka output interval ini dan interval yang overlap itu (dua angka), tapi jika interval ini overlap dengan dua atau lebih interval lain, maka output hanya interval ini (satu angka).

G. Koleksi Perangko
Soal mudah. Jual semua perangko yang pak Janggut punya dan beli lagi perangko-perangko dari harga yang paling murah.

H. Jumlah Data Terurut
Sepertinya ini soal yang paling sulit yang ada di Jollymoo 11. Felix Halim berhasil AC di soal ini, TAPI solusi dia seharusnya masih TLE. Test case yang gw generate untuk soal ini emang ga terlalu kuat, cuma random aja, gw akan generate case criticalnya dan reupload casenya ntar.

Soal ini bisa diselesaikan dengan segment array (gw jelasin di post lain deh) atau segment tree. Solusi segment tree sebenarnya baru kepikiran beberapa hari yang lalu setelah kontes selesai.

Solusi segment tree:
Range bilangan input bisa mencapai 1 miliar, tapi jumlah angka yang berbeda tidak akan lebih dari N, oleh karena itu kita perlu “normalisasi” dulu data-datanya. Caranya? baca dulu semua input dan simpan angka apa saja yang muncul. Ubah angka-angka itu jadi dari 0..X, di mana X adalah jumlah bilangan berbeda yang muncul.

Gunakan segment tree untuk menangani setiap query insert/delete/sum. Setiap node di segment tree perlu menyimpan dua informasi ini:

  • Banyaknya bilangan yang ada di subtree node tersebut.
  • SUM[0..4] dari subtree tersebut.

SUM[0] adalah jumlah semua bilangan kelima dimulai dari index-0: 0, 5, 10, 15, …
SUM[1] adalah jumlah semua bilangan kelima dimulai dari index-1: 1, 6, 11, 16, …
SUM[x] adalah jumlah semua bilangan kelima dimulai dari index-x: x, x+5, x+10, …

Jika kita ingin menghitung SUM[2] dari sebuah node, maka kita hanya perlu menjumlahkan SUM[2] dari node kiri dan SUM[p] dari node kanan, di mana p adalah index yang sesuai dengan jumlah node yang ada di subtree kiri. Misalnya di subtree kiri ada 2 node, maka di subtree kanan kita memerlukan SUM[0] untuk menghitung SUM[2] dari parentnya.

KIRI KANAN
[a b] [c d e f]

c adalah index-0 dari subtree kanan, sehingga untuk menghitung SUM[2] dari parent node, kita perlu menjumlahkan SUM[2] dari node kiri (yang nilainya 0) dan SUM[0] dari node kanan.

I. Tikus Pintar
Ga banyak yang bisa dijelasin, BFS/DFS aja, graphnya kan berupa tree jadi harusnya ga susah.

  4 Responses to “Jollymoo 11”

  1. hai, untuk tahun ini Binus ngadain INC ma ICPC lg nggak? kalo iya kapan?? tx

  2. @atas, seharusnya tetep ngadain kok 🙂

  3. Pak itu untuk E. Himpunan Bilangan Pembagi, apa yang terakhir mustinya 1 = 2^0 * 3^0 ?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)