Jun 112016
 

A. Dividing Sweets

link soal

Diberikan N (1 ≤ N ≤ 100) bilangan bulat (1 atau 2), kelompokkan bilangan-bilangan tersebut ke dalam dua kelompok sedemikian sehingga selisih dari jumlah semua bilangan dari setiap kelompok sekecil mungkin.

Perhatikan bahwa bilangan-bilangan yang diberikan hanya terdiri dari 1 atau 2 saja. Batasan tersebut membuat soal ini bisa diselesaikan dengan mudah. Asumsikan A adalah banyaknya bilangan 1, dan B adalah banyaknya bilangan 2, maka:

  • Jika A ganjil, maka output = 1,
  • Jika A genap dan B genap, maka output = 0,
  • Jika A nol dan B ganjil, maka output = 2.

Soal ini juga bisa diselesaikan dengan mensimulasikan pembentukan kelompoknya: satu per satu setiap bilangan dimasukkan ke dalam kelompok yang jumlahnya lebih kecil. Namun cara ini hanya bisa bekerja jika urutan memasukan bilangannya dimulai dari semua 2, kemudian semua 1 yang tersisa. Jika tidak, solusi ini akan menghasilkan output yang salah. Contoh, {1, 2, 1, 2}. Jika 2 kelompok dibentuk dengan urutan demikian, maka output tidak optimal yang dihasilkan adalah 2: {1, 1} dan {2, 2}.

Jika bilangan yang diberikan tidak memiliki batasan (1 atau 2) maka soal ini adalah partition problem yang merupakan NP-Hard problem (belum diketahui solusi polinomialnya); solusi simulasi di atas juga tidak akan bekerja. Partition problem bisa diselesaikan secara pseudo-polinomial dengan dynamic programming dan batasan N yang cukup kecil di soal ini masih memungkinkan solusi demikian diterima.

B. Lora The Hasty Explorer

link soal

Diberikan sebuah peta grid N x M (1 ≤ N, M ≤ 50) dengan petak mulai/selesai dan tepat 4 petak lain yang berisi artifak, tentukan shortest path untuk mengunjungi semua petak berisi artifak dimulai dari petak awal dan kembali ke petak yang sama.

Peta yang diberikan memiliki 5 petak penting: petak awal/selesai dan 4 petak artifak. Mula-mula, cari dulu shortest path di antara lima petak penting ini (contoh: lakukan BFS sebanyak 5 kali di mulai dari masing-masing petak penting). Kemudian, kita bisa menguji semua rute pengunjungan artifak untuk mendapatkan rute yang paling pendek. Karena ada 4 artifak, maka hanya ada 4! (= 24) rute berbeda.

Alternatifnya, kita juga bisa mendapatkan rute terpendek dengan melakukan satu kali BFS dengan state ⟨baris, kolom, bit_artifak⟩ di mana bit_artifak berisi set artifak yang sudah dikunjungi (implementasi dengan bitmask).

C. Special Formation

link soal

Diberikan N tentara dan N posisi (1 ≤ N ≤ 20) beserta kemampuan setiap tentara untuk menempati posisi yang tersedia (ηx), tentukan ada berapa cara penempatan tentara sedemikian sehingga semua posisi terisi. Modulo hasilnya dengan 1,000,000,007.

Dengan N yang tidak lebih dari 20, soal ini bisa diselesaikan dengan dynamic programming. Kita definisikan f(x, S) sebagai banyaknya penempatan di mana orang berikutnya yang belum menempati posisi adalah x (orang 1..x-1 sudah menempati) dan S adalah set posisi yang masih terbuka. Relasi rekurens dari f(x, S) adalah:

f(x, S) = Σi ∈ {S ∩ ηx} f(x + 1, S \ {i})

dengan f(N>, ∅) = 1.

Berikut adalah contoh implementasi formula relasi rekurens di atas dengan dynamic programming (top down approach).

const int mod = 1000000007;

int dp[maxn][1<<maxn]; // inisialisasi dengan -1

int f(int x, int bit) {
  if ( x == N ) return 1;
  if ( dp[x][bit] != -1 ) return dp[x][bit];
  dp[x][bit] = 0;
  for ( int i = 0; i < can[x].size(); i++ ) {
    int p = can[x][i];
    if ( bit & (1 << p) )
      dp[x][bit] = (dp[x][bit] + f(x+1,bit|p)) % mod;
  }
  return dp[x][bit];
}

// pemanggilan di fungsi main
int ans = f(0,0);

Warning: untested code. Variable bit pada implementasi di atas adalah komplemen dari S (bit = 0 artinya belum ada posisi yang ditempati). Kompleksitas solusi ini adalah O(N * 2N).

D. Counting Substring

link soal

Diberikan sebuah string S (1 ≤ |S| ≤ 200) dan sebuah bilangan bulat K (1 ≤ K ≤ 20,000), tentukan ada berapa banyak cara memilih tepat K substring dari S sedemikian sehingga substring yang terpilih adalah unik di antara substring yang dipilih.

Mula-mula, kita tentukan dulu banyaknya substring pada S dengan menghilangkan substring yang duplikat. Karena panjang string S tidak lebih dari 200, kita bisa melakukan ini secara langsung dengan bantuan container set pada C++ STL atau Set pada Java. Catatan: container set hanya akan menyimpan data secara unik (data yang sama tidak akan disimpan lebih dari satu kopi).

Asumsikan banyaknya substring yang demikian adalah N. Dengan demikian, solusi yang ingin kita dapatkan adalah nck(N, K) % mod.

Kita bisa menggunakan identitas nck berikut: nck(N,K) = N! / K! / (N-K)! untuk menghitung nilai nck(N,K). Perlu diperhatikan bahwa aturan modulo tidak berlaku untuk pembagian, dengan kata lain: (a / b) mod m tidak bisa diubah menjadi ((a mod m) / (b mod m)) mod m. Untuk menangani pembagian, kita bisa menggunakan modular multiplication inverse yang mengubah pembagian menjadi perkalian.

E. Not So Professional Thief

link soal

Diberikan N buah string (1 ≤ N ≤ 100; 1 ≤ |Wi| ≤ 9), tentukan nilai alignment terbesar yang melibatkan semua string yang diberikan.

Kunci penyelesaian soal ini terdapat pada panjang string yang tidak lebih dari 9. Misalkan string pertama yang diberikan adalah A; alignment yang melibatkan semua string pasti juga melibatkan A (by definition). Dengan kata lain, alignment yang melibatkan semua string ada di antara 2|A| potongan string (tidak harus bersambung) yang bisa dihasilkan dari A. Karena panjang string A tidak lebih dari 9, maka banyak potongan string yang bisa dihasilkan dari A tidak lebih dari 29. Setiap potongan string A ini adalah kandidat solusi (yang masih perlu diuji).

Setiap kandidat solusi yang ada perlu diuji: apakah potongan string tersebut terdapat pada semua string yang diberikan. Untuk menguji apakah sebuah string memiliki suatu potongan string bisa dilakukan dalam O(|W|2), nilai ini cukup kecil mengingat |W| ≤ 9.

Dengan demikian total kompleksitas solusi di atas adalah O(2|W| * N * |W|2).

F. Squared Points

link soal

Diberikan N buah titik pada bidang Kartesian (1 ≤ N ≤ 1,000; -1,000 ≤ xi, yi ≤ 1,000), tentukan luas persegi terkecil yang melingkupi semua titik yang diberikan.

Cari titik terkiri dan titik terkanan, hitung selisih jarak x mereka (dx). Cari titik teratas dan titik terbawah, hitung selisih jarak y mereka (dy). Maka sisi persegi terkecil yang diperlukan adalah s = max(dx, dy). Output s2.

G. Number of Divisors

link soal

Diberikan tiga buah bilangan bulat A, B, dan C (1 ≤ A, B, C ≤ 1,000,000; A ≤ B), tentukan berapa banyak bilangan bulat di antara A dan B (inklusif) yang memiliki faktor pembagi sebanyak C. Banyaknya kasus uji adalah T (1 ≤ T ≤ 100,000).

Untuk mempermudah penjelasan, kita definisikan N sebagai banyak bilangan bulat di antara A dan B (inklusif). Salah satu solusi naif yang mungkin “terpikirkan” adalah:

  1. Iterasi semua bilangan bulat X dari A hingga B → kompleksitas: O(N)
  2. Untuk setiap bilangan X, hitung ada berapa faktor pembaginya (serupa dengan cara menguji sebuah bilangan prima) → kompleksitas: O(sqrt(N))

Solusi demikian memiliki total kompleksitas sebesar O(N * sqrt(N)) untuk setiap kasus uji, atau total O(T * N * sqrt(N)); tentunya solusi ini tidak akan bisa menyelesaikan soal ini dalam batas waktu yang diberikan mengingat besarnya N dan T. Saya sengaja membahas sedikit solusi naif di atas karena banyak kontestan yang menggunakan teknik tersebut di soal ini pada saat kontes berlangsung.

Banyaknya faktor pembagi dari semua bilangan 1..1000000 bisa dicari (sekaligus) dengan modifikasi teknik pemangkasan bilangan prima (sieve of eratosthenes).

int nod[1000005] = {0};
for ( int i = 1; i <= 1000000; i++ )
  for ( int j = i; j <= 1000000; j += i )
    nod[j]++;

Potongan kode di atas akan mencari banyaknya faktor pembagi setiap bilangan dari 1 hingga 1000000 yang disimpan di dalam array nod[]. Perhatikan pada iterasi kedua (variable j), perulangan hanya terjadi sebanyak N/i kali (variable j loncat sejauh i di setiap putaran); sehingga total iterasi yang dilakukan pada seluruh kode di atas adalah: N/1 + N/2 + N/3 + ... + N/N, atau bisa disederhanakan menjadi N * (1 + 1/2 + 1/3 + ... + 1/N), atau tidak lebih dari N * log(N) (pelajari tentang Deret Harmonik untuk lebih jelasnya). Dengan demikian, semua faktor pembagi dari 1 hingga 1000000 bisa dicari dalam O(N * log(N)).

Hal berikutnya yang harus kita selesaikan adalah mengatasi jumlah kasus uji yang besar (T ≤ 100,000). Tentunya nilai nod[] (banyaknya faktor pembagi) dari suatu bilangan X akan selalu sama pada kasus uji manapun, sehingga kita tidak perlu berulang kali mencari nilai nod[] untuk setiap kasus uji, cukup satu kali aja.

Kelompokan setiap bilangan ke dalam satu array berdasarkan nilai nod[] nya. Berikut adalah contoh pengelompokan untuk semua bilangan dari 1..20. Sebuah bilangan x berada pada group[y] jika nod[x] = y.

group[1] = {1}
group[2] = {2, 3, 5, 7, 11, 13, 17, 19}
group[3] = {4, 9}
group[4] = {6, 8, 10, 14, 15}
group[5] = {16}
group[6] = {12, 18, 20}

Setelah melakukan pengelompokan demikian, maka kita bisa menjawab pertanyaan C dari setiap kasus uji dengan melakukan binary search (A dan B) pada group[C]. Kompleksitas pencarian dengan binary search hanya O(log(N)). Dengan demikian total kompleksitas solusi di atas adalah O(N*log(N) + T*log(N)).

H. Domino

link soal

Diberikan N kartu domino (1 ≤ N ≤ 100), tentukan jumlah minimum domino tambahan yang diperlukan untuk membentuk sebuah rantai domino yang menggunakan semua kartu yang ada.

Kita bisa merepresentasikan soal ini sebagai problem tentang graph. Setiap kartu domino memiliki dua nilai yang masing-masing berada di antara 0..6, inklusif. Bentuk graph dengan nilai (0..6) sebagai node dan kartu domino (dua nilai) sebagai edge. Dengan demikian, kita memiliki sebuah graph yang hanya terdiri dari 7 node.

Eulerian Path pada sebuah graph adalah rute yang melewati setiap edge yang ada pada graph tersebut tepat satu kali (sedangkan, versi Eulerian Tour nya mengharuskan rute tersebut berakhir di node rute tersebut dimulai – tour). Syarat dari sebuah graph memiliki Eulerian Path adalah:

  • Graphnya terhubung (connected).
  • Terdapat sebanyak-banyaknya dua node dengan degree ganjil.

Jika graph yang kita bentuk terhubung (tidak ada node yang terpisah), maka kita hanya perlu memeriksa ada berapa node dengan degree ganjil pada graph tersebut. Jika 0 atau 2, maka kita tidak perlu menambahkan kartu/edge (terdapat Eulerian Path); jika 4, maka kita perlu menambahkan 1 edge; jika 6, kita perlu 2 edge. Catatan: hanya ada sejumlah genap node yang berdegree ganjil pada sebuah graph.

Bagaimana jika graphnya tidak terhubung? Tambahkan edge seperlunya sedemikian sehingga graphnya terhubung, dan lakukan hal di atas pada graph yang dihasilkan. Ketika menambahkan edge untuk menghubungkan graph, prioritaskan node yang berdegree ganjil sebagai salah satu titik penghubungnya.

I. Life Buddy

link soal

Diberikan N interval [Pi, Qi] dan dua buah bilangan bulat A dan B (1 ≤ N ≤ 20,000; 1 ≤ Pi, Qi, A, B ≤ 100,000; A ≤ B; Pi ≤ Qi), tentukan banyaknya interval minimum yang diperlukan untuk mencakup sebanyak mungkin titik pada rentang [A, B].

Pendekatan greedy bisa digunakan di soal ini. Kita hanya perlu secara terus menerus melakukan hal berikut: pilih interval yang bisa meng-cover titik paling kiri yang belum di-cover dan memiliki titik akhir sejauh mungkin (Qi paling besar). Tentunya dalam menentukan titik terkiri yang belum di-cover, kita perlu mempertimbangkan A (tidak ada gunanya meng-cover titik di kiri A). Selain itu, juga tidak ada gunanya kita meng-cover titik yang lebih kanan dari titik B. Karena N nilainya ≤ 20,000, kita tidak bisa melakukan iterasi terhadap semua interval setiap kali kita mau memilih interval (kompleksitasnya menjadi O(N2)). Urutkan terlebih dahulu semua interval yang ada berdasarkan Pi, sehingga untuk menentukan interval berikutnya yang harus kita pilih, kita bisa memulainya dari posisi pencarian terakhir pada pemilihan interval sebelumnya.

J. Minimum Matrix Cover

link soal

Diberikan sebuah matrix berukuran N x N dan sebuah bilangan bulat K (1 ≤ K ≤ 50), tentukan jumlah nilai terbesar dari tepat K disjoint submatrix persegi di mana setiap petak paling kiri atas dari setiap submatrix berada pada diagonal matrix utama.

Soal ini bisa diselesaikan dengan dynamic programming O(N3). Sebelumnya, hitung dulu P[a][b] untuk semua a dan b, di mana P[a][b] adalah jumlah nilai submatrix persegi yang dimulai dari petak diagonal (a, a) dan berakhir di petak diagonal (b, b). P[a][b] untuk semua a dan b bisa dihitung dalam O(N4) dengan cara melakukan iterasi langsung (brute force, 4 nested loop). Ada cara O(N2) untuk melakukan hal ini, tapi karena nilai N yang cukup kecil (≤ 50), kita tidak memerlukannya di soal ini.

Kita definisikan f(x, k) sebagai jumlah nilai terbesar dari tepat k disjoint submatrix persegi di mana petak paling kiri atas submatrix berada pada diagonal matrix utama dan tidak lebih kecil dari petak (x, x); dengan kata lain, matrix yang menjadi perhatian kita pada f(x, k) adalah [x..N][x..N]. f(x, k) memiliki dua subproblem:

  • Submatrix berikutnya tidak dimulai dari petak (x, x) → f(x + 1, k).
  • Submatrix berikutnya dimulai dari petak (x, x). Pertanyaan berikutnya, berapa besar submatrixnya? Kita bisa menguji semua posisi akhir submatrix untuk mendapatkan hasil yang paling optimal → maxni = x..N P[x][i] + f(i + 1, k - 1).

  6 Responses to “ACM-ICPC 2016 Provincial Sumatra (IdeaFuse)”

  1. Untuk soal a, bisa pakai backtrack ?

  2. Untuk problem G, yang binary search itu harus buat kayak konsep lowerbound sama upperbound y?

    • saya tidak yakin dengan pengertian “lowerbound” dan “upperbound” kamu di sini.

      diberikan array yang berisi sejumlah bilangan dalam keadaan terurut, ada berapa bilangan yang nilainya di antara A dan B. A adalah “lowerbound” dan B adalah “upperbound” dalam pencarian kamu. apa ini maksudnya?

 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)