Jun 282008
 

Problem E. Indomie

Deskripsi Soal E
Problem Author: Felix Halim

Diberikan jumlah indomie tersisa dan panjang antrian, anda diminta untuk menghitung probabilitas Felix mendapat indomie. Soal ini bisa diselesaikan dengan dua pendekatan: kombinatorik dan dynamic programming. Jumlah kombinasi yang bisa terjadi (pada kedua cara) bisa sangat besar dan melebihi batas integer 64-bit, sehingga bisa mengakibatkan overflow. Tipe data double bisa digunakan di soal ini, atau alternatif lain dengan menggunakan BigInteger pada Java.

Kombinatorik
Probabilitas mendapat indomie dapat dirumuskan sebagai:
e1.gif
A = jumlah kombinasi di mana Felix mendapatkan indomie.
B = jumlah semua kombinasi yang ada.

Jumlah kombinasi mendapatkan indomie dapat dihitung dengan:
e2.gif
X = jumlah kombinasi di mana Felix tidak mendapatkan indomie.

Felix tidak mendapatkan indomie jika semua stok indomie habis terdistribusi ke semua orang yang mengantri (n orang).
Jika pilihan yang tersedia hanya indomie dan gula (hanya ada dua pilihan), maka sesuai aturan kombinasi (ada berapa cara mendistribusikan s-indomie kepada n-orang), nilai X adalah:
e3.gif
n = jumlah orang yang mengantri di depan Felix.
s = jumlah indomie yang tersedia.

Karena pilihan non-indomie nya ada dua jenis (gula dan beras), maka kombinasi di atas perlu dikalikan dengan 2(n – s). Di mana (n – s) adalah banyaknya non-indomie yang didistribusikan.
e4.gif
Rumus ini dapat diselesaikan dalam O(s).

Total kombinasi B dapat dihitung dengan menjumlahkan cara mendistribusikan k-indomie kepada n-orang untuk semua k dari 0 s/d s.
e5.gif
Rumus ini dapat diselesaikan dalam O(s2), namun bisa juga dioptimasi menjadi O(s) dengan memanfaatkan hubungan kombinasi (n,k) dengan (n,k-1).
e6.gif

Dynamic Programming
Solusi dynamic programming bisa kita turunkan dari permasalahan ini: banyak cara mendistribusikan maksimal s-indomie kepada n-orang, f(n, s), adalah:

  • berikan gula pada orang paling depan, sub-problem nya menjadi: f(n – 1, s) : jumlah orang berkurang, stok indomie tetap.
  • berikan beras pada orang paling depan, sub-problem nya menjadi: f(n – 1, s) : jumlah orang berkurang, stok indomie tetap.
  • berikan indomie pada orang paling depan, sub-problem nya menjadi: f(n – 1, s – 1) : jumlah orang berkurang, stok indomie berkurang.

Dengan demikian optimal equation untuk problem ini bisa ditulis dalam bentuk:
e7.gif
Formula di atas dapat dikomputasi dalam O(n.s).

Sama seperti cara yang digunakan pada pendekatan kombinatorik, probabilitas Felix mendapatkan indomie dapat dihitung dengan membagi jumlah kombinasi Felix mendapat indomie f(n, s – 1) (banyak cara mendistribusikan maksimal s – 1 indomie) dengan jumlah semua kombinasi f(n, s).

After Thought
Setelah kontes selesai, gw bersama felix dan kurniady sempat membahas ulang soal yang ini (tepatnya kurniady yang jelasin solusi dia). Ternyata di soal ini gw dan felix membuat kesalahan pada cara menghitung probabilitasnya. Bukan solusinya yang salah, tapi… logika soal itu sendiri yang salah šŸ˜€ Salahnya di mana? salahnya adalah: melalui ilustrasi perhitungan di soal itu, ditunjukkan bahwa probabilitas pembagian indomie-beras dengan beras-indomie (urutan dibalik) dianggap sama… padahal seharusnya tidak sama.

A: indomie
B: beras

Jumlah indomie tersedia = 2

Probabilitas kemunculan AABB adalah: 1/2 * 1/2 * 1 * 1 = 1/4
Probabilitas kemunculan BBAA adalah: 1/2 * 1/2 * 1/2 * 1/2 = 1/16

Dua perhitungan terakhir pada AABB adalah 1 karena pada kondisi itu indomienya sudah habis, jadi yang mengantri di urutan ketiga dan seterusnya sudah dipastikan mendapat beras.

Dengan perbedaan probabilitas AABB dan BBAA, maka perhitungan probabilitas mendapat indomie di soal ini tidak bisa dihitung secara kombinatorik n-choose-k seperti di atas šŸ˜€ Solusinya bisa dibuat dengan dynamic programming (sedikit modifikasi dari solusi DP di atas).

Solusi C/C++ (kombinatorik)
oleh Suhendry Effendy

spoiler

#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
  int n, s;
  while ( scanf( "%d %d", &n, &s ) == 2 ) {
    double x = pow(2.0, n - s);
    for ( int i = 1; i <= s; i++ ) x *= (double)(n - i + 1)/i;

    double b = pow(2.0, n), v = 1, w = 1;
    for ( int i = 1; i <= s; i++ ) {
      v *= n - i + 1; w *= i;
      b += pow(2.0, n - i) * v / w;
    }

    printf( "%.5lf\n", (b - x) * 100.0 / b );
  }
  
  return 0;
}

Solusi C/C++ (dynamic programming)
oleh Felix Halim

spoiler

#include <stdio.h>
#include <string.h>

#define MAXN 102

double dp[MAXN][MAXN];
char vis[MAXN][MAXN];

double rec(int n, int s){
  if (n<0) return 0;
  if (n==0) return 1;
  if (vis[n][s]) return dp[n][s]; else vis[n][s] = 1;
  return dp[n][s] = 2*rec(n-1,s) + ( (s>0) ? rec(n-1,s-1) : 0 );
}

int main(){
  for (int n,s; scanf("%d %d",&n,&s)!=EOF; ){
    memset(vis,0,sizeof(vis));
    printf("%.5lf\n", 100.0 * rec(n,s-1) / rec(n,s));
  }
}

Solusi JAVA (kombinatorik)
oleh Suhendry Effendy

spoiler

import java.util.*;

public class Indomie {
  void solve() {
    Scanner scan = new Scanner(System.in);
    while ( scan.hasNextInt() ) {
      int n = scan.nextInt();
      int s = scan.nextInt();
      double x = Math.pow(2.0, n - s);
      for ( int i = 1; i <= s; i++ ) x *= (double)(n - i + 1) / i;

      double b = Math.pow(2.0, n), v = 1, w = 1;
      for ( int i = 1; i <= s; i++ ) {
        v *= n - i + 1; w *= i;
        b += Math.pow(2.0, n - i) * v / w;
      }

      System.out.printf( "%.5f\n", (b - x) * 100.0 / b);
    }
  }

  public static void main(String[] args) {
    new Indomie().solve();
  }
}

  One Response to “Indonesia National Contest 2008: Final Round”

 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)