Chase The Limit

Yup, setelah hampir setahun vakum tidak ngeblog, dan pada tahun 2009 ini saya baru memiliki 1 buah post saja, maka ini akan menjadi post kedua saya pada tahun 2009.

Seperti yang para peserta tahu, Babak kualifikasi BNPCHS 2009, telah usai tadi jam 6 sore, selamat kepada beberapa orang yang sudah memastikan dirinya di babak final. Untuk yang lain, bisa menunggu pengumuman peserta yang melaju ke babak final.

Untuk post kali ini, seperti judulnya, saya akan membahas soal-soal pemrograman yang keluar pada babak penyisihan BNPCHS 2009 tadi. Semoga dengan post ini, anda yang masih belum mengerti caranya, dapat belajar sehingga di babak final nanti, atau bagi yang belum beruntung, hasilnya kedepan akan lebih baik…

Pembahasan ini dapat saya lakukan, karena saya juga mengerjakan soal-soal yang diberikan pada babak penyisihan bersamaan dengan para peserta. Selesai mengerjakan selama kurang lebih 15 menit, saya pun baru mulai membantu juri-juri lainnya untuk men-judge jawaban-jawaban peserta.

Read Full Post »

Yak, babak kualifikasi BNPC-HS 2008 telah usai, disini gua akan menuliskan writeup BNPC-HS 2008 kemarin siapa tau bisa dijadikan bahan belajar buat para finalis yang masih lom pada “Yes - Accepted” di satu, dua, bahkan 3 soal ACM Mode tersebut (Soal Programming. Bukan Soal PG).

Pembahasan ini akan saya bagi menjadi 2, yaitu
1. Story babak pemrograman
2. Pembahasan Soal dan Solusi
3. Advancers

Read Full Post »

For this post, i’ll write it in english instead indonesian language. So, if there are so many gramatical error, you can contact me so i can fix it. Thank You..

In this problem, You are asked to verify Goldbach’s Conjecture for all even numbers less than a million.

What is Goldbach’s Conjecture exactly? in 1742, Christian Goldbach, made a following conjecture:

Every even number greater than 4 can be written as the sum of two odd prime numbers.

for example:

8 = 3 + 5, both 3 and 5 are odd prime numbers.
20= 3 + 17 = 17 + 3.

So, To solve this, we have to generate all odd primes that less than a million. from 3 until 1.000.000 . To generate all primes quickly, there exists a method named Sieve of eratosthenes that can generate primes number very quick in O(n log log n). In this post, i assume you already know this algorithm. Maybe in the next post, i’ll post the details of this algorithm.

First, call the sieve function to generate all the primes, then store the prime numbers in another array. Call it array primes, which contain exactly all primes less than a million.

Then simply iterate from the first odd prime, until the last odd prime (remember, all primes are odd except 2). When iterate, you have to give a simple condition to break the iteration if the current prime is more than the input itself. After that, We just subtract the input with the current prime number, then check whether the result is prime number or not by checking the prime numbers array. if the number exists in the prime array, then print the requested output, then simply break from the iteration.

Checking the result whether this result exists in the prime numbers array or not, can be done in O(lg n) complexity with binary search.

Look at the example:
When the input is 8, our first prime number is 3. then subtract 8 with 3 resulting 5. check whether 5 is prime number by find it at the prime array using binary search algorithm.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include<vector>
#include<cstdio>
#define FOR(i,a,b) for(int i=(a),_n=(b); i<=_n; i++)
#define REP(i,n) FOR(i,0,(n)-1)
using namespace std;
vector<int> primes;
void sieve(int n) {
	vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false;
	int i;
	for (i=2; i*i<=n ; i++ ) {
		if (is_prime[i]) {
			if (i!=2) primes.push_back(i);
			for(int j=i*i; j<=n; j+=i) is_prime[j]=false;
		}
	}
	if (i%2==0) i++;
	for(i;i<=n;i+=2) if (is_prime[i]) primes.push_back(i);
}
 
int bs(int left, int right, int x) {
	int mid;
	while (left<=right) {
		mid = (left + right) / 2;
		if (primes[mid] == x) return 1;
		if (x<primes[mid]) {
			right = mid - 1;
		} else {
			left=mid+1;
		}
	}
	return 0;
}
 
int main() {
	sieve(1000002);
	int n;
	while (scanf("%d", &n)!=EOF && n!=0) {
		REP(i,primes.size()) {
			int b = n - primes[i];
			if (bs(i,primes.size()-1,b)) {
				printf("%d = %d + %d\n", n,primes[i],b);
				goto end;
			}
		}
		puts("Goldbach's conjecture is wrong.");
		end:;
	}
	return 0;
}

How about your approach? So, if you have any approach that simplier than this one and you don’t mind to share it with us (me and other readers), just post your approach in the comment.

Thank You..

- Felix J

Read Full Post »

Combination ( Kombinasi a.k.a nCk )

Dalam ilmu matematika, sebuah kombinasi itu adalah gabungan beberapa objek dari suatu grup tanpa memperhatikan urutan. Jadi, {5,4,6} sama aja dengan {4,5,6}

Kombinasi biasanya dipake untuk menyelesaikan soal seperti ini:
Ada berapa kombinasi jika kamu hanya bisa membawa 3 pensil dari 4 pensil yang tersedia?

Continue Reading »

Read Full Post »

Halo semua, untuk para pembaca blog-ku yang sepi ini dan masih berstatus sebagai siswa SMU, dan tentu saja doyan ma yang namanya Programming (Espescially Algoritma), cuman mau kasi tau bahwa BNPC-HS 2008 akan segera dimulai.

Jangan sampe ketinggalan lho, karena event ini kalo menang bisa Kuliah Gratis di Jurusan Teknik Informatika Binus (untuk IPA), atau di Jurusan Sistem Informasi / Komputerisasi Akuntansi Binus (untuk IPS), dan tentu saja punya kesempatan untuk memperkuat Binus Programming Team .

Buat yang gak tau, BNPC-HS (BiNus Programming Contest for High School) adalah Kontes pemrograman yang diadakan tahunan oleh Binus University untuk level SMA (High School), dan lombanya itu bersifat perorangan.

Penyisihan:
7 Desember 2008, Jam 13.30 - 16.30
- Soal berupa Pilihan Ganda (50 nomer). Materi : Seputar Algoritma, B. Pemrograman, dan Pengetahuan tentang Ilmu Komputer
- Soal pemrograman (ACM Mode) sebanyak 3 Problem.

Perlu diingat bahwa Penyisihan ini bersifat Online Contest, Jadi kalian Online dari Rumah (atau mana saja) untuk mengerjakan 50 soal PG + 3 Problem Soal Pemrograman (ACM Mode). Jika tidak dapat menemukan koneksi internet yang baik ( atau kesusahan untuk mencari koneksi internet ), Binus University menyediakan ruang lab untuk meng-akomodasi Online contestnya. Tinggal dateng aja ke Kampus Anggrek Binus university lantai 6… 25 orang peserta terbaik & 2 orang terbaik dari masing-masing SMU akan lolos ke Babak Final.

Babak Final :
14 Desember 2008, Jam 09.00 - 16.30
Untuk Final, Soalnya adalah Soal Programming (ACM Mode).

Perlu diingat bahwa untuk babak Final ini, sifatnya adalah Onsite Contest. Jadi anda harus datang ke Binus University untuk mengikuti Final BNPC-HS 2008 ini. Contest akan diselenggarakan di Lab Software Binus University lantai 6.

Compiler / Software yang digunakan:
Untuk lomba ini, disediakan BC31, DevC++, Java 6, dan FPC 2.2.0

Hadiah :
# Champion, 1 Orang: Hadiah berupa Uang Tunai Rp. 2.500.000,00 + Plakat + Piagam + Bebas biaya studi di Prodi Teknik Informatika untuk lulusan IPA, dan Sistem Informasi / Komputerisasi Akuntansi untuk lulusan IPS di BINUS University (146 SKS).
# Medali Emas, 2 Orang: Hadiah berupa Uang Tunai Rp. 1.750.000,00 + Medali + Piagam
# Medali Perak, 3 Orang: Hadiah berupa Uang Tunai Rp. 1.250.000,00 + Medali + Piagam
# Medali Perunggu, 4 Orang: Hadiah berupa Uang Tunai Rp. 1.000.000,00 + Medali + Piagam

Pendaftaran:
Pendaftaran bisa langsung dateng ke Admisi di Kampus Anggrek Binus University
atau dengan pendaftaran online yang bisa dilakukan di link ini.

Informasi Lebih Lanjut silahkan ke:
Customer Service BNPC-HS 2008
u.p. Sdri. Vera dan Sdri. Friska.
Ruang Admisi BINUS UNIVERSITY
Kampus Anggrek, Jl. Kebon Jeruk Raya No.27,
Kebon Jeruk, Jakarta Barat 11530
Telp. (021) 53-69-69-69 / (021) 53-69-69-99
Fax (021) 535-0655
e-mail : lombati@binus.ac.id

Untuk lebih lengkapnya silahkan bisa ke Homepage BNPC-HS 2008 langsung di http://competition.binus.ac.id/

Ayo buruan daftar… Jangan lewatin kesempatan untuk bisa Kuliah Gratis di Binus

*Untuk Contoh Soal, bisa liat disini, dan juga ada arsipnya disini, dan beberapa pembahasan disini, dan disini*

Enjoy Learning selama 2 minggu lebih ini agar bisa tampil di Final bagi yang mengikuti lomba ini

Read Full Post »

Hoaammm… Udah lama juga sejak gua terakhir kali update ini blog. Setelah kelar sekitar seminggu lebih ACM/ICPC ini baru aja bisa update blog dengan tulisan ini :p . Karena kemarin itu setelah ICPC selesai, besoknya langsung ke Bandung… Jadi yah baru ada waktu hari ini. Sebenarnya banyak yang ingin diceritain sih… tapi gua mulai ceritain dlu dari ACM/ICPC baru Gemastik dan yang lainnya y… :p *stay tuned on my blog !! :p *

Ini gua bagi menjadi beberapa halaman biar bacanya enak dan terstruktur :p *apa sih? :p *

Hari H-1 : Notebook & Mental Preparation.
Hari H : Registration, Opening Ceremony, & Practice Contest.
Hari H+1 : Contest Proper, Excursion, & Closing Ceremony.

My Team :
Team Name : Gomenix
Consists of :
1. Felix Jingga (Me, Teknik Informatika 2008)
2. Johan Lemena (Teknik Informatika 2007)
3. Garry Linford (Teknik Informatika 2007)

Read Full Post »

Pada post kali ini, saya akan membahas tentang operasi bitwise… Mengapa ada post ini? agar orang yang membaca pada post sebelumnya (Baca: [Algorithm] Swap Two Values) mengerti tentang cara yang ke-3 yang diajarkan pada post sebelumnya itu…

Apa itu bitwise operation? *Ada yang tau? * Humm… Bitwise Operation adalah operasi yang dilakukan dalam tingkatan satuan bits…

Masih tertarik setelah mendengar kata-kata diatas? kalo ya, Mari kita lanjutkan… *Kalo gk, ya… jangan diterusin… beresiko ntar tuhh~~ hehehe… j/k j/k*

Continue Reading »

Read Full Post »

Minggu (1/6/2008), aku mencoba untuk mengikuti INC 2008 Qualification Round jadi peserta tersembunyi *Thanks to Bapak Suhendry telah memberikan izin :)* mencoba-coba untuk solve problems… INC 2008 untuk babak Qualification ini memiliki 5 problems yang harus diselesaikan sekitar 3 jam (jam 1.00 - 4.00), tapi aku baru bisa login pada 1 jam terakhir, karena Pak Suhendry ternyata sedang super sibuk, jadi baru bs diberikan sekitar hampir 1jam sebelum selesai.. (So, aku hanya punya waktu 1 jam untuk membaca, memikirkan solusi dan mengkodingnya dengan benar).

Kita mulai saja… *Lanjutkan ke halaman berikutnya…*

Read Full Post »

Untuk post kali ini, masih berhubungan dengan post yang sebelumnya. Pada post kali ini, saya akan menjelaskan beberapa teknik untuk menukar nilai dari 2 variabel. maksudnya jika kita mempunyai variabel a dengan nilai 1 dan variabel b dengan nilai 2. maka setelah kita tukar nilainya, variabel a mempunyai nilai 2 dan variabel b mempunyai nilai 1.

Tertarik dengan Tema ini?
Continue Reading »

Read Full Post »

GCD - LCM / FPB - KPK… Greatest Common Divisors - Lowest Common Multiples ato Faktor Persekutuan Terbesar - Kelipatan Persekutuan Terkecil adalah salah satu pelajaran matematika yang pernah kita dapatkan sewaktu SD… Masih ingatkah anda? Coba buka-buka lagi dhe buku pas SD dlu :P hehehehe… kalo gk ada, yah dengan post ini, saya coba bantu ingatkan anda dengan contoh yang simpel…
Continue Reading »

Read Full Post »