Chase The Limit

Problem A : Bujur Sangkar Ajaib

Problem ini sebenarnya sudah sering kita liat ketika tayangan film The Master. Untuk menyelesaikan problem ini, sebenarnya jika anda tidak tahu caranya pun, google bisa menjadi teman anda

Sebuah Bujur Sangkar Ajaib, yaitu magic square, mempunyai semua angka dari 1 sampai dengan n^2. Untuk n = 3, yaitu sebuah magic square 3×3, maka magic square tersebut pasti mempunyai angka dari 1 … 3^2 yaitu 1 … 9 ! dan tentu saja ini adalah magic constant terkecil yang dapat tercapai. Sehingga untuk menjawab soal ini, anda hanya perlu menjumlahkan dari 1 … n^2. itu adalah jumlah untuk semua baris. Sehingga untuk mendapatkan jumlah perbaris, maka kita harus membaginya dengan n. Solusi saya adalah sebagai berikut

#include<stdio.h>
int main() {
	int ntc;
	scanf("%d", &ntc);
	while(ntc--) {
		int n, res = 0;
		scanf("%d", &n);
		for(int i=1; i<=n*n; i++) res += i;
		printf("%d\n", res / n);
	}
	return 0;
}

Solusi di atas, memiliki kompleksitas O(n^2).

Ada sebuah cara lagi untuk menjawab pertanyaan diatas, dengan menggunakan rumus deret, dimana rumus tersebut adalah (n * ( n^2 + 1 ) / 2). Rumus ini diturunkan dari deret penjumlahan diatas. Solusi kedua saya adalah sebagai berikut

#include<stdio.h>
int main() {
	int ntc;
	scanf("%d", &ntc);
	while(ntc--) {
		int n;
		scanf("%d", &n);
		printf("%d\n", n * (n*n + 1) / 2);
	}
	return 0;
}

Solusi kedua ini memiliki kompleksitas O(1) untuk tiap input yang diberikan.

Jika anda melakukan googling dengan kata “magic square”, halaman wiki tentang soal ini telah memberitahukan rumus diatas, sehingga dapat langsung anda pakai untuk menyelesaikan soal ini.

Problem B : Menghitung Palindrom

Problem ini, kita dihadapkan untuk menghitung ada berapa kalimat palindrom yang terdapat pada string yang diberikan.

Pertama, kita harus mengetahui bahwa definisi bilangan palindrom, adalah bilangan yang ketika dibaca dari belakang, dan dari depan, sama. contohnya, “katak”, “kodok”, dlsbnya…

Kedua, dapat kita simpulkan bahwa, semua sub-kata yang mempunyai panjang 1, merupakan palindrom. Kemudian, seperti yang dijelaskan pada soal, kita harus mencoba mengecek mulai dari sub-kata yang panjang 1, kemudian 2, sampai dengan kata itu sendiri. Untuk tiap sub-kata, kita mengecek, apakah itu prima / tidak. Maka solusi dari soal tersebut adalah sebagai berikut

#include<stdio.h>
#include<string.h>
int palin(char *s) {
	int _n = strlen(s);
	for(int i=0, j = _n-1; i<j; i++, j--)
		if ( s[i] != s[j] ) return 0;
	return 1;
}
 
void substr( char *s, int k, int i, char *t) {
	char ret[ strlen(s) + 2 ];
	int idx = 0;
	for(int x=k, to = k+i; x<to; x++) ret[idx++] = s[x];
	ret[idx] = '\0';
	strcpy(t, ret);
}
int main() {
	int ntc;
	scanf("%d", &ntc);
	while(ntc--) {
		char s[120], temp[120];
		scanf("%s", s);
		int ans= 0;
		for(int i=1, _n=strlen(s); i <= _n; i++) {
			for(int k=0; k+i <= _n; k++) {
				substr(s, k, i, temp);
				if ( palin(temp) ) ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Selain solusi diatas, saya juga mempunyai solusi yang di buat dalam C++ yang memanfaatkan STL String. Berikut adalah solusi kedua dari saya

#include<stdio.h>
#include<string>
using namespace std;
 
int palin(string s) {
	int _n = s.size();
	for(int i=0, j = _n-1; i<j; i++, j--)
		if ( s[i] != s[j] ) return 0;
	return 1;
}
int main() {
	int ntc;
	scanf("%d", &ntc);
	while(ntc--) {
		char s[120];
		scanf("%s", s);
		string ss = s;
		int ans= 0;
		for(int i=1, _n=ss.size(); i<=_n; i++) {
			for(int k=0; k+i <= _n; k++) {
				string ns = ss.substr(k,i);
				if ( palin(ns) ) ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Solusi saya untuk problem ini memiliki kompleksitas O( |S|^3 ), dimana |S| maksimal 100. Sehingga kompleksitas ini masih kecil dan tentu saja pasti melewati time limit 2s yang diberikan.

Jika panjang karakter yang diberikan lebih besar, maka cara di atas tentu saja tidak dapat melewati batas waktu yang diberikan. Sehingga kita perlu menurunkan kompleksitas algoritma yang kita miliki, sehingga menjadi O( |S|^2 ).

Cara untuk menurunkannya adalah sebagai berikut. Untuk tiap index, maka kita jadikan dia pusat, dan kita perpanjang ke kiri dan kanan. Sehingga jawaban ada berapa banyak palindrom yang dapat dibentuk dari pusat tersebut adalah sebanyak berapa kali kita dapat perpanjang ke kiri dan ke kanan. Itu berlaku untuk palindrom yang memiliki panjang ganjil. Untuk panjang genap, kita jadikan titik ini dan titik selanjutnya menjadi pusat, kemudian perpanjang ke kanan dan ke kirinya. Setelah mendapat berapa banyak kita dapat perpanjang ke kiri dan ke kanan dengan berasumsi panjang palindromnya ganjil, dan panjang palindrom genap. Kita tinggal menambahkan kedua jawaban tersebut ke variabel jawaban kita.

Implementasi solusinya adalah sebagai berikut

#include<stdio.h>
#include<string.h>
int expand( char *s, int idx, int len, int mode) {
	int left = idx, right = (!mode) ? idx : idx+1, ret = 0;
	while( (0 <= left && right < len) && s[left] == s[right])
	       ret++, left--, right++;
	return ret;
}
int main() {
	int ntc;
	scanf("%d", &ntc);
	while(ntc--) {
		char s[120];
		scanf("%s", s);
		int ans = 0;
		for(int i=0, _n=strlen(s); i < _n; i++) {
			ans += expand(s, i, _n, 0) + expand(s, i, _n, 1);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Fungsi expand adalah fungsi untuk memperpanjang ke kiri dan ke kanan. Jika mode adalah 0, maka fungsi tersebut meng-asumsikan panjang palindromnya adalah ganjil. Sebaliknya jika mode adalah 1, maka fungsi tersebut meng-asumsikan panjang palindrom adalah genap.

Problem C : String Prima

Untuk problem ini, anda diharuskan mencari bilangan prima terbesar, yang ada pada string yang diberikan.

Solusi untuk soal ini cukup mudah. Pertama, kita menggenerate semua bilangan prima dari 1 sampai 1000. Kemudian mulai dari bilangan prima terbesar, anda turun ke bilangan prima terkecil. Untuk setiap bilangan prima, cek apakah di string tersebut, terdapat bilangan prima tersebut.

Untuk mengecek apakah ada bilangan prima tersebut pada string yang diberikan, anda rubah bilangan prima yang semula bertipe data integer / bilangan bulat, menjadi string. kemudian mulai dari index ke 0 dari bilangan yang diberikan, dan mulai dari index ke 0 pada string prima tersebut. Majukan index yang menunjuk string yang diberikan. Jika karakter pada index yang ditunjuk di string yang diberikan, sama dengan karakter pada index yang ditunjuk pada string prima, maka majukan index yang menunjuk string prima.

Implementasi dari solusi di atas, dapat dilihat pada source code berikut

#include<stdio.h>
#include<string.h>
int prima[169];
int isp(int n) {
	int ret = 0;
	for(int i=1; i<=n; i++)
		if ( n%i == 0 ) ret++;
	if ( ret == 2 ) return 1;
	else return 0;
}
int calc() {
	prima[0] = 2;
	int idx = 1;
	for(int i=3; i<=1000; i+=2) if ( isp(i) ) prima[idx++] = i;
	return idx;
}
int exists( int n, char *s) {
	char ss[10];
	sprintf(ss, "%d", n);
	int idx = 0, nlen = strlen(ss);
	for(int i=0, _n = strlen(s); idx < nlen && i<_n; i++) {
		if ( ss[idx] == s[i] ) idx++;
		if ( idx == nlen ) break;
	}
	if ( idx == nlen ) return 1;
	else return 0;
}
int main() {
	// Generate Prima
	int nprima = calc();
	int ntc;
	scanf("%d", &ntc);
	while(ntc--) {
		char s[200];
		scanf("%s", s);
		int ret = -1;
		for(int i=nprima-1; i>=0; i--) {
			if ( exists( prima[i], s) ) {
				ret = prima[i];
				break;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}

Cara di atas, walau tidak benar-benar efisien, dapat melewati seluruh testdata juri dengan waktu kurang lebih 0.16s… Tidak diperlukan algo yang aneh dan tingkat tinggi untuk menyelesaikan soal ini. Kompleksitas Algoritma untuk yang ini terbilang rendah untuk tiap testcase, yaitu O( k * |S| ) dimana k adalah banyaknya bilangan prima dari 1 - 1000, dan |S| adalah panjang dari string yang diberikan untuk tiap masukan. Kemudian untuk menggenerate 168 bilangan prima diperlukan waktu O(499^2), Sehingga total kompleksitas program di atas adalah O( 499^2 + t * k * |S| ), dimana t adalah banyaknya input.

Untuk soal, mungkin akan dipublish nantinya pada website resmi BNPCHS 2009. Kalau mau dilihat, sebenarnya tidak ada soal yang susah dari soal-soal tersebut. Tingkat kesulitan soal babak penyisihan ini pun lebih mudah daripada soal tahun lalu.

Untuk yang maju pada babak final, saya tidak tahu pasti kapan akan diumumkan peserta yang melaju ke babak final. Tetapi, saya berharap agar semua peserta yang dapat maju ke babak final untuk datang pada babak final, sehingga menambah pengalaman anda.

Sampai Jumpa di BINUS Pada tanggal 6 desember 2009. Good Luck, and Have Fun !

Pages: 1 2