Start From Your Dream: Pembahasan Babak Penyisihan BNPCHS 2015

Halo, selamat pagi/siang/sore/malam. Pada tanggal 2 Agustus kemarin, teman-teman dari SMA seluruh Indonesia baru saja melaksanakan babak penyisihan BNPCHS 2015 secara online. Total ada 6 soal dengan tingkat kesulitan Division 2 problem A/B (jika dibandingkan dengan soal dari kontes Codeforces).

Yang pertama kali mencapai skor penuh adalah username sergioveri dari SMA Intan Permata Hati dengan Last Accepted Submission di menit ke 24 untuk soal F. Untuk scoreboard penuh dapat dilihat pada tautan berikut : https://jollybeeoj.com/user/contest/5/scoreboard

Berikut adalah pembahasan singkat dari soal-soal babak penyisihan.

Problem A - Ini Ibu Budi

Author : Suhendry Effendy

Ini merupakan permasalahan paling mudah pada babak penyisihan. Input yang diberikan 2 bilangan A dan B. Tugas kita adalah menjumlahkan A sebanyak B kali. Dengan kata lain, cukup cetak A * B.

Sebagia besar, peserta tidak memperhatikan format output yang sudah diberikan di soal. Contohnya, jika input 10 20, maka output peserta dapat berupa :

200 (salah, karena tidak ada 'Kasus #X: ')
KASUS #1: 200 (salah, karena 'KASUS' seharusnya 'Kasus')
Kasus #1:200 (salah, karena setelah ':' harus diberikan tepat satu spasi)
Kasus #1: 200 (benar, format output sesuai yang diminta soal).

Pada tahun ini, tidak ada yang mengeluarkan output tambahan untuk meminta input (contoh, "Masukkan Input", "Input : "). Hal ini menunjukan sebagian besar para peserta sudah mengerti cara mengambil input pada kontes competitive programming, meskipun banyak yang masih kurang teliti dalam menangani output.

C++ Solution : Suhendry Effendy

#include < bits/stdc++.h >
using namespace std;

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;
}

Pascal Solution : Teddy Budiono

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. Kita dapat lihat jika keadaan tombol sedang berada pada kondisi CINTA, maka dia akan berubah menjadi TIDAK CINTA, begitu juga sebaliknya. Hal yang harus dilakukan adalah mengecek apakah penekanan yang dilakukan Sandi merupakan bilangan genap atau ganjil.

Pada soal ini, sebagian besar peserta salah menganalisis penekanan yang dilakukan Sandi. Jika kita lihat pada contoh input output, maka penekanan pertama akan menghasilkan "CINTA", lalu diikuti dengan "TIDAK CINTA", dan seterusnya. Dengan kata lain, jika penekanan yang dilakukan adalah ganjil, maka Sandi akan menekan tombol CINTA, jika penekanannya genap, maka Sandi akan menekan tombol TIDAK CINTA.

Banyak peserta yang terbalik dalam menganalisis ganjil genap tersebut. Hal ini seharusnya langsung diketahui peserta karena pada contoh input output jelas tidak akan sama. Berarti peserta masih tidak memperhatikan contoh input output yang diberikan, sehingga dapat memberikan tambahan penalti 20 menit untuk soal tersebut.

Disisi lain, peserta juga sering melakukan kesalahan cetak kata 'CINTA' / 'TIDAK CINTA' dengan mencetak dengan huruf kecil atau hanya huruf depan yang besar.

C++ Solution : Teddy Budiono

#include < cstdio >

int tc;
void solve() {
  int N;
  scanf("%d", &N);
  printf("Kasus #%d: ", tc);
  if (N % 2) puts("CINTA");
  else puts("TIDAK CINTA");
}

int main() {
  int T;
  scanf("%d", &T);
  for (tc = 1; tc <= T; tc++) solve();
  return 0;
}

Pascal Solution : Teddy Budiono

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

Beberapa peserta mungkin terlalu berlebihan berpikir untuk menyelesaikan soal ini. Soal ini dapat diselesaikan tanpa menggunakan Sorting sama sekali. Yang harus dilakukan adalah, hitung ada berapa orang dengan nilai yang lebih besar dari Tedy. Maka, jawabannya adalah banyaknya orang tersebut.

Di soal ini, banyak peserta yang menggunakan cara yang berlebihan dengan cara mensort terlebih dahulu, lalu mengecek nilai yang < dari Tedy. Hal ini membuat peserta melakukan kesalahan jika ternyata Tedy peringkat terakhir (nilai Tedy merupakan nilai paling kecil). Peserta tidak melakukan inisialisasi variabel dengan benar (kebanyakan 0) sehingga jika Tedy memiliki nilai terkecil, peserta akan mencetak 0.

C++ Solution : Teddy Budiono

#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) {
    int x;
    scanf("%d", &x);
    if (x > M) ans++;
  }
  printf("Kasus #%d: %d\n", tc, ans);
}

int main() {
  int T;
  scanf("%d", &T);
  for (tc = 1; tc <= T; tc++) solve();
	return 0;
}

Pascal Solution : Teddy Budiono

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, kalian 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.

Lalu 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.

C++ Solution : Teddy Budiono

#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;
}

Pascal Solution : Teddy Budiono

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

Jika kalian perhatikan, roda gigi akan berjalan dengan lancar jika tidak ada roda gigi yang searah disebelah kanan atau kirinya. Dengan demikian, kondisi roda gigi yang valid hanya akan ada 2.

LRLRLRLRLRLR........
RLRLRLRLRLRL........

Jadi kita tinggal mengecek ada berapa karakter yang berbeda dengan kondisi tersebut.

Banyak peserta yang sudah mengetahui bahwa roda gigi harus berbeda arah putarannya dengan sebelahnya. Namun sebagian besar peserta hanya langsung berpatokan dengan roda gigi pertama. Mereka lupa bahwa roda gigi pertama bisa kita set menjadi 'L' / 'R'. Seperti contoh 'LLRLRLR', jawaban peserta akan mengeluarkan 6 yang membuat roda gigi menjadi 'LRLRLRL', padahal solusi optimalnya adalah mengubah roda gigi yang paling depan menjadi 'R' sehingga menjadi 'RLRLRLR'.

C++ Solution : Teddy Budiono

#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;
}

Pascal Solution : Teddy Budiono

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

Pada soal ini, kalian belajar menggunakan Big Mod dimana jika jawaban terlalu besar, kalian diminta untuk mencetak jawaban kalian dengan dimodulo sesuatu. Solusinya adalah dengan mengimplementasi teori yang sudah dijelaskan di soal.

Beberapa masalah yang dihadapi peserta saat menjawab soal F 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.

C++ Solution : Teddy Budiono

#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;
}

Pascal Solution : Teddy Budiono

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.

Kesalahan umum yang masih sering dilakukan peserta :

Peserta tidak memperhatikan format output yang diminta soal.
Banyak peserta yang melakukan validasi input. Input juri dijamin ada didalam batasan yang tertera. Jadi peserta tidak perlu melakukan validasi input. Hal ini akan memakan waktu kalian dalam mengerjakan soal.

Para peserta yang berhasil lolos ke babak final dapat dilihat pda tautan berikut : http://competition.binus.ac.id/bnpchs2015/index/final

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 flag be with you :)

*Soal akan dipublish dalam waktu dekat

Start From Your Dream

Tuesday, August 4, 2015

Pembahasan Babak Penyisihan BNPCHS 2015

No comments:

Post a Comment