Pada 5 Agustus kemarin, 140 siswa SMA dari 66 sekolah mengikuti BNPCHS 2018. Dari 3.5 jam waktu pengerjaan, ada 90 peserta yang melakukan percobaan dengan 90% submission menggunakan bahasa C/C++. Dari 6 soal dengan tingkat kesulitan yang menyebar, 2 peserta berhasil menyelesaikan semua soal dengan rata-rata peserta berhasil menyelesaikan 2.67 soal dan median 3 soal.
Pada editorial ini, kami akan membahas solusi dari setiap soal disertai dengan kesalahan-kesalahan yang sering dilakukan oleh peserta.
Soal: A, B, C, D, E, F
Terdapat N buah snack yang dibawa oleh tokoh utama dan terdapat K orang teman. Apakah jumlah snack tersebut dapat dibagi habis kepada semua orang?
Sekilas, problem ini terkesan meminta anda untuk menghitung apakah N habis dibagi K. Akan tetapi ketika membaca soal lebih teliti, terdapat statement dimana tokoh utama akan membagi snack tersebut kepada dirinya dan K orang temannya (.. Kemudian ia dan K orang temannya masing masing akan menerima sejumlah snack. ..) sehingga anda diminta untuk mengecek apakah N habis dibagi (K+1). Soal ini memang ditujukan agar peserta teliti dalam membaca soal.
Problem ini merupakan problem termudah pada babak penyisihan dan berhasil diselesaikan oleh 75 peserta dengan rata-rata 3.22 submissions dari tiap peserta. Kesalahan yang sering dilakukan oleh peserta selain kurang teliti dalam membaca di antaranya:
Berikut salah satu solusi Pascal yang accepted:
var t, _t: integer; n, k: longint; begin readln(t); for _t := 1 to t do begin readln(n, k); k := k + 1; write('Kasus #', _t, ': '); if(n mod k = 0) then begin writeln('ya'); end else begin writeln('tidak'); end; end; end.
Diberikan angka A dan B dengan A ≤ B. Apakah hasil penjumlahan semua angka dari A hingga B termasuk dalam bilangan negatif, nol, atau positif.
Problem ini tidak dapat dilakukan langsung dengan menjumlahkan semua bilangan dari A hingga B. Akan tetapi, dengan melihat fakta bahwa suatu angka P + (-P) akan menghasilkan angka nol, anda dapat melakukan sedikit optimasi sehingga problem ini dapat dilakukan tanpa menggunakan perulangan dari A hingga B. Perhatikan bahwa jika -A = B maka setiap angka positif akan dikurangi dengan negatifnya sehingga menghasilkan 0, maka 0 hanya akan menjadi jawaban ketika -A = B, sisanya kita hanya perlu melihat apakah -A > B (Negatif) atau -A < B (Positif).
Problem ini merupakan problem termudah kedua pada babak penyisihan dengan rata-rata 3.34 submissions tiap peserta. Kesalahan yang sering dilakukan oleh peserta adalah tidak memperhatikan tipe data yang sesuai untuk menampung angka dari input.
var t,_t:integer; a,b:int64; begin readln(t); for _t:=1 to t do begin readln(a,b); write('Kasus #',_t,': '); if(-a=b) then begin writeln('Nol'); end else if(-a<b) then begin writeln('Positif'); end else begin writeln('Negatif'); end; end; end.
Diberikan 2 buah dadu yang memiliki N buah sisi dengan masing-masing sisi dadu tersebut terdapat sebuah angka yang berbeda-beda dari 1 sampai N dan masing-masing pemain akan memegang 1 buah dadu. Pemain pertama akan memilih sebuah angka di antara 1 sampai (N-1). Setelah itu, kedua pemain akan melempar dadunya masing-masing. Jika angka maksimum yang muncul pada sisi dadu yang menghadap ke atas lebih kecil atau sama dengan angka yang dipilih pemain pertama maka, pemain pertama memenangkan permainan tersebut. Angka berapa yang harus dipilih oleh pemain pertama agar kemungkinan pemain pertama menang lebih besar dari pemain kedua dengan syarat selisih kemungkinan menang mereka sekecil mungkin?
Soal ini merupakan soal probabilitas dimana anda harus menguji angka X terkecil yang memenuhi permintaan soal dimana X sebagai angka dimana kedua dadu memiliki angka lebih kecil atau sama dengan X. Oleh karena itu, probabilitas dari kedua dadu yang memenuhi syarat X adalah (x/n)2 (didapat dari probabilitas dadu pertama kurang dari sama dengan X dikali dengan probabilitas dadu kedua). Akan tetapi, konstanta N yang besar menyebabkan anda tidak dapat menguji setiap angka X yang dipilih karena time complexity yang dibutuhkan melebihi permintaan juri. Oleh karena itu, anda dapat mengoptimasi proses pengujian angka X berdasarkan fakta yang didapat dari soal.
Fakta 1: jika adalah kemungkinan pemain pertama menang dengan memilih sebuah angka X, maka dapat dipastikan f(x) > f(x+1). Fakta 2: untuk mengecek apakah kemungkinan pemain pertama menang lebih besar dari pemain kedua apabila pemain pertama memilih sebuah angka X, anda dapat menggunakan pertidaksamaan x2/n2 > 1/2.
Berdasarkan fakta 1, soal ini dapat diselesaikan menggunakan Binary Search untuk mencari angka terkecil yang dapat dipilih oleh pemain pertama. Tetapi, beberapa solusi mendapatkan verdict Wrong Answer karena lupa menguji apakah terdapat sebuah angka yang memenuhi pertidaksamaan pada fakta 2. Jika tidak terdapat angka yang memenuhi fakta 2, maka cetak -1.
Soal ini juga dapat diselesaikan menggunakan persamaan matematika biasa. Melihat fakta bahwa x2/n2 > 1/2 dan kita ingin mencari nilai X, maka jawabannya adalah akar dari (n2/2). Hati-hati ketika meng-output-kan jawaban dari sebuah akar, anda harus mengubah tipe data double menjadi tipe data integer terlebih dahulu.
var t, _t: integer; n, l, r, m: int64; function f(x: int64): boolean; var p, q: int64; begin p := x * (x-1) + x; q := n * n; f := false; if(p > q - p) then f := true; end; begin readln(t); for _t := 1 to t do begin readln(n); write('Kasus #', _t, ': '); l := 1; r := n; while(l < r) do begin m := (l+r) div 2; if(not f(m)) then begin l := m + 1; end else begin r := m; end; end; if(l = n) then writeln(-1) else writeln(l); end; end.
Pengetahuan yang dibutuhkan: terminologi graf, manipulasi bit, struktur data Disjoint Set.
Diberikan sebuah weighted undirected graph dengan N vertices dan M edges. Total nilai keindahan dari sebuah perjalanan adalah bitwise operator OR untuk setiap jalan yang dilalui. Apakah terdapat rute perjalanan dari vertex 1 menuju vertex N dengan total nilai keindahan sebesar X? Sebuah jalan dapat dilalui lebih dari 1 kali.
Fakta: suatu edge dapat dilalui apabila semua bit yang menyala pada weight jalan tersebut merupakan subset dari semua bit yang menyala pada X.
Berdasarkan fakta 1, dapat disimpulkan bahwa terdapat setidaknya sebuah rute yang valid apabila terdapat sebuah connected component dengan hanya menggunakan edge yang memenuhi fakta 1 dan memenuhi kriteria berikut:
Untuk mengecek apakah terdapat connected component yang memenuhi kriteria di atas dapat dengan menggunakan algoritma BFS/DFS atau struktur data Disjoint Set.
Pengetahuan yang dibutuhkan: struktur data heap.
Diberikan array dengan panjang 3N. Setiap element berisi sebuah bilangan bulat. Hapus N elements di dalam array sehingga selisih antara N elements awal dan N elements terakhir memiliki nilai semaksimal mungkin.
Dari deskripsi di atas, soal ini meminta anda untuk membagi array tersebut menjadi 2 bagian dengan besar minimal sebesar N elements. Ketika array tersebut sudah terbagi menjadi 2 bagian, anda diminta untuk memilih N elements terbesar pada segment kiri dan N elements terkecil pada segment kanan sehingga selisih dari kedua segments menjadi semaksimal mungkin. Hal ini dapat kita lakukan untuk N+1 kemungkinan untuk membagi array.
Melihat fakta bahwa soal ini memiliki constraint N yang besar, solusi naive tidak dapat dilakukan sehingga anda membutuhkan sedikit optimasi untuk menyelesaikan soal ini. Anda dapat membuat sebuah tabel prefix maximum sum (tabel yang menyimpan jumlah dari N elements terbesar ketika memulai dari segment kiri) dan sebuah tabel suffix minimum sum (tabel yang menyimpan jumlah dari N elements terkecil ketika memulai dari segment kanan) dengan menggunakan struktur data heap. Ketika 2 tabel tersebut telah terbentuk, anda dapat mencoba N+1 kemungkinan titik tengah dengan langsung mengacu pada tabel tersebut.
Diberikan sebuah tree khusus dengan N vertices. Terdapat Q queries dalam 2 tipe format, yaitu tipe 1 yang bertujuan untuk meng-update “biaya melintas” pada suatu edge tertentu dan tipe 2 yang bertujuan untuk mencari biaya perjalanan antara 2 leaves tertentu.
Secara naive, solusi ini dapat diselesaikan menggunakan BFS/DFS (graph traversal). Akan tetapi, time complexity untuk solusi tersebut melebihi waktu yang diberikan oleh juri. Oleh karena itu, anda diminta untuk mencari cara yang lebih optimal dengan melihat beberapa keistimewaan yang terdapat pada tree tersebut.
Fakta 1: kota metropolitan (kota dengan degree lebih dari 2) eksklusif membentuk sebuah connected tree. Fakta 2: jumlah kota metropolitan paling banyak adalah 100. Fakta 3: cost antara 2 kota metropolitan tidak akan diubah.
Melihat 3 fakta diatas, anda dapat mengoptimalkan proses perhitungan biaya transportasi antara 2 kota metropolitan dengan cara memasangkan semua kemungkinan dari kota metropolitan (sekitar 100 X 100 kemungkinan) karena dipastikan rute akan melewati minimal 1 kota metropolitan. Selain itu, kita juga dapat merepresentasikan ulang tree tersebut menjadi star-model tree (tree dengan maksimal 1 vertex yang memiliki degree lebih dari 2, sebut saja vertex O). Oleh karena itu, perjalanan dari kota industri menuju vertex O memiliki biaya transportasi yang dapat disimpan ke dalam 1 tabel biaya transportasi. Ketika terdapat query tipe 1, kita dapat langsung menambahkan biaya tersebut pada tabel biaya transportasi yang melewatinya. Dipastikan bahwa update tersebut hanya berlaku pada persis 1 path dari kota industri menuju vertex O.