Sunday, September 9, 2012

BNPCHS 2012 Penyisihan


Halo malam semua. Barusan tadi pagi saya jadi judge di BNPCHS 2012 yang tiap tahun diadakan Binus University untuk tingkat SMA. Jika salah satu dari kalian di judge oleh judge8, nah itu saya :D. Babak penyisihan baru saja berlalu dan link score board dapat dilihat disini : LINK. 2 Tahun  lalu saya adalah peserta BNPCHS 2012, kemudian BNPCHS saya menjadi Dummy (Peserta Bayangan), dan sekarang menjadi judge :)).

Babak pertama adalah babak PG (Pilihan Ganda). Tiap peserta diberikan soal sebanyak 50 buah soal logika dan beberapa potongan program. Beberapa soal juga saya yang membuat. Yang ada VINCENTIUS atau VINCENTnya itu saya yang buat :P (Narsis Dikit). Nah peserta diberikan waktu 50 menit (1 menit tiap soal tetapi ada waktu bonusnya untuk tiap soal) untuk mengerjakan soal tersebut. Waktu login yang fleksibel dari jam 09.00 sampai jam 10.00 membuat ada peserta yang selesai lebih dulu atau ada yang masih mengerjakan. Yang saya amati adalah peserta dari sekolah saya (SMA Strada Santo Thomas Aquino) yang mengirimkan beberapa pesertanya. Beberapa menit, rata rata peserta Thomas benar 2 (4 %) :'( agak mengecewakan tetapi beberapa lama, Janitra (J_Avila) naik melejit ke ranking 26 Wow lumayan lah ada harapan :D. Tetapi beberapa lama tidak bergerak dan akhirnya turun. Pikiran saya sih mungkin waktu pengerjaannya udah habis makanya tidak bisa menambah point. Untuk peserta Thomas yang lain bener bener harus banyak banyak banget belajar dan latihan serta banyak mengasah logika.

1 Jam berlalu di babak PG dan untuk peserta Thomas sepertinya kurang persiapan :'(. Peserta diberikan waktu 30 menit untuk istirahat sebelum babak programing mulai. Disela sela waktu, ruang juri sangat berisik apa lagi ko Felix Jingga yang ngambil makan gak kira kira (3 Kotak yang alasannya sih mau dikasih ke ko Christian Simon :P) dan langsung ditaruh di depan kompinya (Saya Lapar langsung :'( ). 

Singkat cerita, setengah jam berlalu dan juri bersiap untuk serbuan submission. Benar juga sebelum 3 menit ada peserta yang submit soal A (Soal bonus) dan tentunya Accepted. Beberapa peserta juga langsung menyusul soal A. Tapi lagi banyaknya submission soal A, ada langsung submission untuk soal B (Sepertinya mudah juga) yang ternyata Accepted. dan tentu saja sebelum 15 menit berlalu sudah ada yang sapu bersih oleh imiro (IOI tahun ini kan dia ?). Lalu menyusul nathanajah (ini juga IOI tahun ini) dan beberapa peserta lainnya. Ruang juri juga gak kalah semangatnya mengklik refresh untuk rebutan judge. Entah kenapa judge2 kecepatannya seperti BOT. Sekalinya muncul Submission langsung diambil X_X.

Ada satu judge namanya tukangnasgor. Kalau kalian di judge oleh dia maka kalian harus membeli nasgornya :)). Dia adalah Teddy Budiono (Maav kalo namanya salah :D). Dengan account khusus, sepertinya dia juga banyak menjudge >.< dan gw kalah banyak sepertinya. Mendekati tengah tengah kontest ada peserta yang hanya copas dari tokilearning dan mensubmitnya. WOW bagaimana dia bisa seperti itu >_<. Tapi untung saja hanya satu peserta. Ada error lucu yang membingungkan juga. Include library C yang harusnya stdio.h ditulis studio.h tapi anehnya dia submit (Apa di compilernya gak Compile Error yah o_o).

Di akhir kontest ada ko kurniady yang mau ikutan juga jadi peserta bayangan. Dengan bermodalkan notepad (Kalau gak salah) dan kodingan yang rata kiri, langsung menghajar soal B. meskipun sempat salah, tetapi sebelum kontest berakhir sudah sapu bersih (Kalau gak salah dia mulainya 11.45). Tim Thomas juga saya bingung masih tidak ada submission. Satu satunya datang dari Janitra tapi dia submit jawaban soal A di soal B >.<. Pas dia submit di soal A ternyata memang Wrong Answer. Haduh kalian kan bisa lihat internet kalau tidak mengerti array atau if then else atau looping. Jangan mentang mentang kalian belum sampai array (bab 2 tokilearning) kalian tidak bisa mengerjakan o_o. Jaman saya, jangankan tokilearning, kurikulum pascal pun tidak ada.

Oke ini saya kasih penjelasan singkat tentang soal pemrograman penyisihan tadi. Saya coding di pascal untuk kalian latihan lebih mudah (Tetapi saya codingnya lebih sulit T_T). Oke ini pembahasannya.

Soal A : Kotak mainan windi.

Soal ini menjadi soal bonus di penyisihan kali ini. Kalian cukup simulasikan saja untuk setiap A dan B yang diberikan, cek ada berapa bilangan yang berada dalam rentang A dan B eksklusif (A dan B tidak termasuk). Cukup cuma itu. Batas bilangan yang kecil (N = 100, M(Query) = 10) jadi kompleksitas 100 * 10 sangat cukup.
program bangke;
var
        t, i, j, kasus, answer, a, b, n, m : longint;
        arr : array [1..1000] of longint;
begin
        readln(t);
        kasus := 0;
        while t > 0 do
        begin
                t := t - 1;
                inc(kasus);
                readln(n, m);
                writeln('Kasus #',kasus,':');
                for i := 1 to n do read(arr[i]);
                for i := 1 to m do
                begin
                        answer := 0;
                        readln(a, b);
                        for j := 1 to n do
                        begin
                                if (arr[j] < b) and (arr[j] > a) then
                                        inc(answer);
                        end;
                        writeln(answer);
                end;
        end;
end.

Soal B : Kata Rahasia.

Harusnya ini jadi soal tergampang kedua. Soal ini typical Ad-Hoc String. kita hanya perlu memecah mecah stringnya berdasarkan spasi dan kemudian disimpan dalam satu array. kemudian buatlah fungsi untuk menguubah dari bahasa alay menjadi bahasa normal dan jangan lupa huruf kecil semua tiap kata. Kemudian cetak dalam urutan terbalik. namun hati hati dalam pencetakan. jangan sampai ada spasi tambahan di akhir baris. Di code dibawah ini ada fungsi fungsi baru seperti length(), ord(). kalian coba cari sendiri apa maksud dari fungsi tersebut.


program bangke;

var
        k, t, i, pan, kasus, jumlah_kalimat, n : longint;
        temp, kalimat, huruf : ansistring;
        arr : array [1..1000] of ansistring;
        cek : array [1..1000] of boolean;
        j : char;

function ubah(A : ansistring) : ansistring;
begin
        huruf := 'oizeasgtbq';
        temp := '';
        for k := 1 to 1000 do cek[k] := false;
        for j := 'a' to 'z' do
                cek[ord(j)] := true;
        for j := 'A' to 'Z' do
                cek[ord(j)] := true;
        for j := '0' to '9' do
                cek[ord(j)] := true;
        for k := 1 to length(A) do
        begin
                if cek[ord(A[k])] = true then
                        temp := temp + A[k];
        end;
        for k := 1 to length(temp) do
        begin
                if (ord(temp[k]) - ord('0') <= 9) then
                        temp[k] := huruf[ord(temp[k]) - ord('0') + 1];
        end;
        temp := lowercase(temp);
        ubah := temp;
end;


begin
        readln(t);
        kasus := 0;
        while t > 0 do
        begin
                t := t - 1;
                inc(kasus);
                readln(jumlah_kalimat);
                readln(kalimat);
                pan := length(kalimat);
                i := 1;
                n := 1;
                temp := '';
                repeat
                        if kalimat[i] <> ' ' then
                                temp := temp + kalimat[i]
                        else begin
                                arr[n] := temp;
                                inc(n);
                                temp := '';
                        end;
                        inc(i);
                until (i > pan);
                arr[n] := temp;
                for i := 1 to n do
                begin
                        arr[i] := ubah(arr[i]);
                end;
                write('Kasus #',kasus,': ');
                for i := n downto 1 do
                begin
                        write(arr[i]);
                        if i > 1 then write(' ')
                        else writeln;
                end;
        end;
end.


Soal C : Ganda Campuran.
Soal ini merupakan soal tersulit. tidak seperti soal soal sebelumnya, soal ini minimal harus mengerti sorting dan binary search. Sorting yang harus digunakanpun harus extra seperti merge-sort (LINK). Pertama setelah selesai berurusan dengan input, kita sort pada bagian pemain wanita dengan urutan menaik. Setelah itu lakukan looping dari pemain pria dan cari batas pada pemain wanita dengan binary search. setelah mendapatkan batasnya maka secara logika kalau pemain pria + pemain wanita[batas] lebih besar dari batasnya, maka pemain wanita diatasnyapun jika dijumlah dengan pemain prianya akan lebih besar dari batas. maka tidak perlu dicek lagi. Kompleksitas saat mensort adalah O(N log N) + saat mencari N log N (Binary search). Banyak yang mengira ini adalah soal termudah kedua karena mudah dipahami dan mudah dikoding tetapi banyak yang tidak menghitung kompleksitasnya sehingga banyak yang mendapat Time Limit Exceeded.


program bangke;
var
        mid, i, j, k, n, l, r, pria, wanita, t, batas, answer, kasus : longint;
        arr, buff, co : array [1..100000] of longint;

procedure sort(A : longint; B : integer);
var
        i, j, k, mid : longint;
begin
        if (A < B) then begin
                mid := (A + B) div 2;
                sort(A, mid);
                sort(mid+1, B);
                i := A;
                j := mid+1;
                k := A;
                while ((i <= mid) and (j <= B)) do
                begin
                        if (arr[i] < arr[j]) then
                        begin
                                buff[k] := arr[i];
                                inc(i);
                        end
                        else begin
                                buff[k] := arr[j];
                                inc(j);
                        end;
                        inc(k);
                end;
                while i <= mid do
                begin
                        buff[k] := arr[i];
                        inc(i);
                        inc(k)
                end;
                while j <= B do
                begin
                        buff[k] := arr[j];
                        inc(j);
                        inc(k);
                end;
                for i := A to B do
                        arr[i] := buff[i];
        end;
end;

begin
        readln(t);
        kasus := 0;
        while t > 0 do
        begin
                t := t - 1;
                inc(kasus);
                readln(pria, wanita, batas);
                for i := 1 to pria do read(co[i]);
                for i := 1 to wanita do read(arr[i]);
                answer := 0;
                sort(1, wanita);
                for i := 1 to pria do
                begin
                        l := 1;
                        r := wanita;
                        while l < r do
                        begin
                                mid := (l + r) div 2;
                                if co[i] + arr[mid] < batas then
                                        l := mid + 1
                                else r := mid;
                        end;
                        if co[i] + arr[l] >= batas then answer := answer + 1;
                        answer := answer + (wanita - l);
                end;
                writeln('Kasus #',kasus,': ',answer);
        end;
end.

Oke sekian pembahasannya. Semoga beruntung masuk final :).

Berikut daftar peserta dari SMA Strada Santo Thomas Aquino :
dragonnarm
christian widjaya
sma strada santo thomas aquino
andre wijaya
andre wijaya
SMA STRADA ST. THOMAS AQUINO
onny_riani@ymail.com
Leonny Noveriani
sma strada santo thomas aquino
UnknownG
Devin
SMA Strada Santo Thomas Aquino
hudacings1
Husni Al Huda
SMA Strada St. Thomas Aquino
D.Daeg
Didit Indiarto
SMA Santo Thomas Aquino
Reynaldo Stefanus
Reynaldo Stefanus
SMA Strada St. Thomas Aquino
J_Avila
Janitra Avila Budiono
SMA STRADA ST. THOMAS AQUINO
rexyxaverius
Rexy Jonathan R
Strada St. Thomas Aquino
richard erwin
richard erwin
sma strada st thomas aquino
wiranatakb
Wiranata Kusuma Budiono
SMA Strada Santo Thomas Aquino
alfon
Alfontius Linata
SMA Strada Santo Thomas Aquino
lass26
Jonathan
SMA STRADA SANTO THOMAS AQUINO

No comments:

Post a Comment