Berikut adalah ulasan babak penyisihan BNPCHS 2015 yang baru saja berlalu. Ulasan ini ditulis oleh Vincentius Madya Putra yang juga dimuat di blog-nya.

Pada tanggal 2 Agustus 2015, teman-teman dari SMA seluruh Indonesia baru saja melaksanakan babak penyisihan BNPCHS 2015 secara online. Total ada 6 soal dengan tingkat kesulitan yang cukup mudah.

Yang pertama kali mencapai skor penuh adalah peserta dengan username sergioveri dari SMA Intan Permata Hati dengan last accepted submission pada menit ke 24 untuk soal F. Untuk scoreboard penuh dapat dilihat pada tautan berikut

Berikut adalah pembahasan singkat dari soal-soal babak penyisihan.

Problem A - Ini Ibu Budi

Author: Suhendry Effendy

Ini merupakan soal paling mudah pada babak penyisihan. Diberikan input berupa 2 buah bilangan bulat, A dan B. Tugas kita adalah menjumlahkan A sebanyak B kali; dengan kata lain, hitung A * B (A dikali B).

Sebagian besar, peserta tidak memperhatikan format output yang ditentukan soal. Contohnya, apabila input yang diberikan adalah 10 20 (outputnya 200), beberapa kesalahan output yang bisa ditemui dari program peserta, antara lain:

• 200 (salah, karena tidak ada keluaran 'Kasus #X: ')
• KASUS #1: 200 (salah, karena 'KASUS' seharusnya 'Kasus')
• Kasus #1:200 (salah, karena setelah ':' harus diberikan tepat satu spasi)

Tahun ini tidak ada yang mengeluarkan output tambahan yang tidak diminta soal (ct: "Masukan Input: ", "Input: ", dan lainnya). Hal ini menunjukan bahwa sebagian besar para peserta sudah mengerti cara mengambil input pada kontes competitive programming, meskipun banyak yang masih kurang teliti dalam menangani output.

#include <cstdio>
 
int main()
{
  int T;
  scanf( "%d", &T );
  for ( int tc = 1; tc <= T; tc++ ) {
    int a, b;
    scanf( "%d %d", &a, &b );
    printf( "Kasus #%d: %d\n", tc, a * b );
  }
  return 0;
}

var
  T, tc : integer;
  A, B : integer;
begin
  readln(T);
  for tc := 1 to T do begin
    readln(A, B);
    writeln('Kasus #', tc, ': ', A*B);
  end;
end.

Problem B - Penggemar Berat

Author: Vincentius Madya

Terdapat 2 kondisi tombol. Yang pertama adalah CINTA, yang kedua adalah TIDAK CINTA; jika status tombol sedang berada pada kondisi CINTA, maka status tersebut akan berubah menjadi TIDAK CINTA dengan satu penekanan, begitu juga sebaliknya. Dengan demikian, kita hanya perlu memeriksa apakah banyak penenakan tombol yang dilakukan Sandi adalah ganjil atau genap. Jika ganjil maka statusnya adalah CINTA, jika genap maka statusnya TIDAK CINTA.

Beberapa peserta terbalik dalam menganalisis ganjil-genap tersebut. Hal ini seharusnya bisa langsung diketahui jika peserta menguji programnya dengan contoh input-output yang diberikan di soal. Selain itu, beberapa peserta juga masih melakukan kesalahan ketika menuliskan output 'CINTA' atau 'TIDAK CINTA' dengan huruf kecil (atau hanya huruf pertama yang kapital).

#include <cstdio>
 
int main() {
  int T;
  scanf("%d", &T);
  for ( int tc = 1; tc <= T; tc++ ) {
    int N;
    scanf( "%d", &N );
    printf( "Kasus #%d: ", tc );
    if ( N % 2 == 0 )
      puts( "TIDAK CINTA" );
    else
      puts( "CINTA" );
  }
  return 0;
}

var
  T, tc: integer;
  N: integer;
begin
  readln(T);
  for tc := 1 to T do begin
    readln(N);
    write('Kasus #', tc, ': ');
    if N mod 2 = 0 then writeln('TIDAK CINTA')
    else writeln('CINTA');
  end;
end.

Problem C - Deduksi Peringkat

Author: Gilbert Wonowidjojo

Kita hanya perlu menghitung ada berapa orang yang memiliki nilai lebih besar dari Tedy, dan itulah jawabannya.

Solusi beberapa peserta terlihat berlebihan dengan menggunakan sorting terlebih dahulu (catatan: metode di atas tidak perlu sorting sama sekali). Beberapa peserta (cukup banyak) juga melakukan kesalahan dengan tidak menginisialisasi variable output. Contohnya, ketika metode yang digunakan adalah dengan mengurutkan data secara menurun, kemudian mencari index terkecil di mana P'_i lebih kecil atau sama dengan M, maka itulah output yang dikeluarkan. Metode ini tidak akan mengeluarkan output, atau output yang dikeluarkan adalah 0, jika M adalah data yang paling kecil (tidak ada satupun di antara P yang ≤ M).

#include <cstdio>
 
int main() {
  int T;
  scanf("%d", &T);
  for ( int tc = 1; tc <= T; tc++ ) {
    int N, M, P;
    int rank = 1;
    scanf( "%d %d", &N, &M );
    for ( int i = 0; i < N; i++ ) {
      scanf( "%d", &P );
      if ( P > M ) rank++;
    }
    printf( "Kasus #%d: %d\n", tc, rank );
  }
  return 0;
}

var
  tc, T, i: integer;
  N: integer;
  M: longint;
  ans: integer;
  tmp: longint;
begin
  readln(T);
  for tc := 1 to T do begin
    readln(N, M);
    ans := 1;
    for i := 1 to N do begin
      read(tmp);
      if (tmp > M) then ans := ans + 1;
    end;
    writeln('Kasus #', tc, ': ', ans);
  end;
end.

Problem D - Kacamata Anti-Akik

Author: Gilbert Wonowidjojo

Pada soal ini, kita harus melakukan implementasi yang diminta soal. Salah satu cara implementasinya adalah, cari bagian kiri batu dan bagian kanan batu yang terhubung, anggap L untuk index kiri, dan R untuk index kanan, selama L < R, ubah S[L++] = S[R--] = '.'. Lakukan terus selama masih ada 2 batu yang bersebelahan. Banyak cara untuk mengimplementasi solusi, peserta hanya perlu berhati hati dalam mengimplementasikannya.

#include <cstdio>
#include <cstring>
 
int tc;
char data[200];
void solve() {
  scanf("%s", data);
  int N = strlen(data);
  for (int i = 0; i < N; i++) {
    if (data[i] == 'X') {
      int bts = i;
      while(bts < N && data[bts] == 'X') bts++;
      for (int j = i; j < bts; j++) data[j] = '.';
      if ((bts - i) % 2) data[(i+bts)/2] = 'X';
      i = bts-1;
    }
  }
  printf("Kasus #%d: %s\n", tc, data);
}
int main() {
  int T;
  scanf("%d", &T);
  for (tc = 1; tc <= T; tc++) solve();
  return 0;
}

var
  T, tc : integer;
 
procedure solve;
var
  S : string;
  i, j, k : integer;
  pjg : integer;
begin
  readln(S);
  pjg := length(S);
   
  i := 1;
  while i <= pjg do begin
    if S[i] = 'X' then begin
      j := i;
      while (j <= pjg) and (S[j] ='X') do j := j + 1;
      for k := i to j-1 do S[k] := '.';
      if (j-i) mod 2 = 1 then S[(i+j) div 2] := 'X';
      i := j-1;
    end;
    i := i + 1;
  end;
   
  writeln('Kasus #', tc, ': ', S);
end;
 
begin
  readln(T);
  for tc := 1 to T do begin
    solve;
  end;
end.

Problem E - Roda Gigi

Author: Vincentius Madya

Roda gigi hanya bisa bekerja jika tidak ada roda gigi di sebelah kanan atau kirinya yang arah putarannya sama. Dengan demikian, kondisi roda gigi yang valid hanya ada 2:

• LRLRLRLRLRLR...
• RLRLRLRLRLRL...

Dengan demikian, kita hanya perlu mengecek ada berapa karakter yang berbeda dari dua kondisi tersebut, output yang paling kecil.

Banyak peserta yang memahami cara pengecekan di atas. Namun beberapa peserta hanya berpatokan pada arah putaran roda gigi pertama. Mereka lupa bahwa roda gigi pertama juga bisa kita ubah putarannya. Contoh, 'LLRLRLR', jawaban peserta (yang salah) akan mengeluarkan 6 yang membuat roda gigi menjadi 'LRLRLRL', padahal solusi optimalnya adalah mengubah roda gigi (hanya 1) yang paling depan menjadi 'R' sehingga menjadi 'RLRLRLR'.

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const double PI = acos(-1);
const double EPS = 1e-7;
 
#define PB push_back
#define MP make_pair
#define FOR(_i, _from, _to) for (int (_i) = (_from), (_batas) = (_to); (_i) <= (_batas); (_i)++)
#define REP(_i, _n) for (int (_i) = 0, (_batas) = (_n); (_i) < (_batas); (_i)++)
#define SZ(_x) ((int)(_x).size())
 
int tc;
char data[1005];
void solve() {
  int N;
  scanf("%d", &N);
  scanf("%s", data);
   
  int cost1 = 0, cost2 = 0;
  REP(i, N) { cost1 += data[i] == (i%2?'L':'R'); cost2 += data[i] == (i%2?'R':'L'); }
  printf("Kasus #%d: %d\n", tc, min(cost1, cost2));
}
 
int main() {
  int T;
  scanf("%d", &T);
  for (tc = 1; tc <= T; tc++) solve();
    return 0;
}

var
  tc, T: integer;
  i: integer;
  N, cost1, cost2, ans: integer;
  S: ansistring;
 
begin
  readln(T);
  for tc := 1 to T do begin
    readln(N);
    readln(S);
     
    cost1 := 0;
    cost2 := 0;
    for i := 1 to N do begin
      if i mod 2 = 0 then begin
        if S[i] = 'L' then cost1 := cost1 + 1
        else cost2 := cost2 + 1;
      end
      else begin
        if S[i] = 'R' then cost1 := cost1 + 1
        else cost2 := cost2 + 1;
      end;
    end;
     
    ans := cost1;
    if cost2 < cost1 then ans := cost2;
    writeln('Kasus #', tc, ': ', ans);
  end;
end.

Problem F - ROKET-1

Author: Vincentius Madya

Di soal ini, kita perlu melakukan op perkalian/pangkat dengan modulo. Kita hanya perlu mengimplementasikan teori yang diberikan di soal ke dalam program kita. Untuk setiap A * B, ubah menjadi ((A mod M) * (B mod M)) mod M.

Beberapa masalah yang dihadapi peserta saat menjawab soal ini adalah test data 0 1. Banyak peserta yang mencetak 1, sedangkan jawaban yang sebenarnya adalah 0. Sebagian besar disebabkan karena mereka tidak memodulo hasil akhir, sehingga ketika pangkatnya 0, tidak ada operasi modulo yang dipanggil sehingga sebagian peserta mencetak variabel awal yang bernilai 1.

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const double PI = acos(-1);
const double EPS = 1e-7;
 
#define PB push_back
#define MP make_pair
#define FOR(_i, _from, _to) for (int (_i) = (_from), (_batas) = (_to); (_i) <= (_batas); (_i)++)
#define REP(_i, _n) for (int (_i) = 0, (_batas) = (_n); (_i) < (_batas); (_i)++)
#define SZ(_x) ((int)(_x).size())
 
int tc;
void solve() {
  int N, M;
  scanf("%d %d", &N, &M);
  int ans = 1;
  REP(i, N) ans = (ans * 10) % M;
   
  printf("Kasus #%d: %d\n", tc, ans % M);
}
 
int main() {
  int T;
  scanf("%d", &T);
  for (tc = 1; tc <= T; tc++) solve();
    return 0;
}

var
  tc, T, i: integer;
  N, M, ans: longint;
begin
  readln(T);
  for tc := 1 to T do begin
    readln(N, M);
    ans := 1 mod M;
    for i := 1 to N do ans := (ans * 10) mod M;
    writeln('Kasus #', tc, ': ', ans);
  end;
end.

Selain "tidak memperhatikan format output yang diminta soal", beberapa peserta juga menuliskan validasi input pada program mereka. Input yang digunakan juri dijamin sesuai dengan ketentuan soal (sesuai dengan batasan yang tertera), sehingga kita tidak perlu melakukan validasi input.

Peserta yang berhasil lolos ke babak final dapat dilihat pada tautan berikut: here

Selamat untuk para finalis, dan persiapkan diri kalian karena soal final akan lebih menantang dari babak penyisihan :)

Sampai jumpa di babak final. Goodluck and have fun. May the flags be with you :)

-- Vincentius Madya Putra