Pembahasan Soal Codeforces – 1131B

CONTEST

Soal berjudul Draw! ini merupakan bagian dari contest  Codeforces Round #541 (Div 2). Pembahasan pada post kali ini dibuat menurut pemahaman penulis, sedangkan pembahasan official dari tim pembuat soal bisa dicek di  Official Editorial Codeforces.

SOAL

Diketahui dalam sebuah pertandingan sepak bola, panitia mencatatkan informasi skor kedua tim sebanyak beberapa kali, sesuai waktu yang telah ditentukan (momen). Informasi tersebut dicatat sebanyak $n$ kali dengan penulisan berpasangan $(a_i,b_i)$. Ini menunjukkan bahwa pada saat tertentu dalam pertandingan, skornya adalah $a_i : b_i$. Jika diketahui skor sekarang adalah $(x : y)$, maka apabila sebuah gol terjadi, skor di papan saat itu berubah menjadi $x+1 : y$ atau $x : y+1$.

Berapakah banyak kemungkinan skor seri terjadi selama pertandingan tersebut berlangsung?

Input

Baris input pertama terdiri dari sebuah integer $n$ $(1 \leq n \leq 10000)$  — banyaknya pencatatan yang dilakukan panitia (banyak momen).

Setiap baris dari total $n$ baris berikutnya terdiri dari integer $a_i$ dan $b_i$  $(0 \leq a_i,b_i \leq 109)$, yang menyatakan skor pertandingan pada momen tersebut (jumlah gol dari tim pertama dan gol dari tim kedua).

Semua momen diinputkan secara terurut, sehingga sekuens $x_i$ dan $y_j$ non-decreasing. Skor terakhir yang tercatat merupakan skor final dari pertandingan tersebut.

Output

Print banyak kemungkinan skor seri terjadi selama pertandingan tersebut berlangsung. Skor $(0:0)$ pada awal pertandingan juga dihitung seri.

Contoh dan pembahasan

Contoh Pertama
input $n$ dan skor tiap momen:

output banyak skor seri:

Pada momen ke-1 skor tim $a$ adalah 2 dan skor tim $b$ adalah 0. Pada momen tersebut jika dijabarkan semua skor yang mungkin terjadi sebelum pencatatan adalah $\{(0,0),(1,0),(2,0)\}$, sehingga skor seri yang pernah terjadi adalah $(0,0)$. Pada momen ke-2 skor berubah untuk tim $a$ menjadi $3$ dan tim $b$ skor menjadi $1$. Pada momen ini, skor yang mungkin terjadi adalah $\{(2,1),(3,1)\}$ dimana tim $b$ mencetak gol lebih dulu atau sebaliknya tim $a$ duluan yang mencetak gol dengan skor $\{(3,0),(3,1)\}$. Dari kedua opsi tersebut diketahui bahwa tidak ada skor seri yang mungkin terjadi. Terakhir, momen ke-3 terjadi penambahan gol untuk tim $b$ secara berturut-turut yang dibuktikan dengan tidak bertambahnya skor tim $a$ dari momen terakhir pencatatan. Maka dari itu skor yang terjadi sebelum pencatatan pada momen ini adalah $\{(3,2),(3,3),(3,4)\}$ dimana terjadi skor seri yakni $(3,3)$.

Total dari 3 momen pencatatan tersebut ada sebanyak 2 kali skor seri, seperti yang terlihat di tabel berikut.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 2 & 0 & \{(0,0)\} \\
2 & 3 & 1 & \{ \} \\
3 & 3 & 4 & \{(3,3)\}
\end{array}
$$

Contoh Kedua
input $n$ dan skor tiap momen:

output banyak skor seri:

Pada contoh ini, skor kedua tim tidak berubah/bertambah dari awal momen sampai akhir. Maka skor seri yang memungkinkan hanya 1 kali, yakni $(0,0)$ itu sendiri.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 0 & 0 & \{(0,0)\} \\
2 & 0 & 0 & \{\text{ } \} \\
3 & 0 & 0 & \{\text{ } \}
\end{array}
$$

Contoh Ketiga
input $n$ dan skor tiap momen:

output banyak skor seri:

Pada contoh ini hanya terjadi satu kali momen pencatatan dengan skor $(5,4)$. Dengan melihat minimal skor di antara kedua tim kita dapat menentukan bahwa skor seri yang mungkin terjadi adalah semua skor yang dimulai dari $0$ sampai dengan skor minimal di momen tersebut $\min{(5,4)} = 4$, sehingga ada sebanyak 5 kali skor seri seperti pada tabel di bawah ini.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 5 & 4 & \{(0,0),(1,1),(2,2),(3,3),(4,4)\}
\end{array}
$$

Pembahasan

Cara menghitung banyaknya skor seri dalam suatu pertandingan dapat disederhanakan dengan mencari kemungkinan skor seri di setiap momen pencatatan. Di setiap momen pencatatan, hal yang perlu diperhatikan adalah minimal skor pada momen saat ini yakni $\min{(x_i,y_i)}$ dan maksimal skor pada momen sebelumnya yakni $\max{(x_{i-1},y_{i-1})}$. Nilai yang menjadi patokan tiap momen adalah nilai $\min{(x_i,y_i}) – \max{(x_{i-1},y_{i-1})}$ yang pada langkah-langkah di bawah ini kemudian ditulis dengan $s$. Nilai $s$ ini merupakan banyaknya skor seri yang mungkin pada tiap momen.

Pertama, kita akan menyimpan total banyaknya skor seri pada suatu variabel $T$ tentunya di awal inisialisasi dengan 0 (baris 2 kode python).

Perlu diingat bahwa permulaan pertandingan skor $(0,0)$ merupakan seri sehingga inisialnya kita sudah menyimpan 1 nilai seri. Untuk mempermudah, asumsi bahwa skor yang tercatat pada momen $(i-1)$ adalah seri diterapkan di perhitungan tiap momen, ditunjukkan dengan penambahan nilai $s$ dengan $1$ di awal perhitungan tiap momen (baris 9 kode python).

Kedua, jika $s$ adalah positif, maka ada perubahan skor pada momen $(i)$ sekarang dibanding dari momen $(i-1)$ sebelumnya, yang memungkinkan adanya skor seri di momen $i$ ini (baris 10 kode python).

Ketiga, jika skor yang dicatat pada momen $(i-1)$ sebelumnya merupakan skor seri, maka pada momen sekarang $(i)$ tidak perlu dihitung ulang. Sehingga penyimpanan skor seri dikurangi, yakni dengan mengkurangkan nilai $s$ dengan $1$ (baris 14 kode python). Selain itu, maka total banyaknya skor seri $T$ ditambahkan dengan nilai $s$ pada momen $(i)$ ini (baris 12 kode python). Proses ini diulangi sampai sejumlah momen pencatatan pada input atau sejumlah $n$.

Pembahasan Soal Codeforces – 1100C (Part 1)

CONTEST

Soal berjudul NN and the Optical Illusion ini merupakan bagian dari contest  Codeforces Round #532 (Div 2). Pembahasan pada post kali ini dibuat menurut pemahaman penulis, sedangkan pembahasan official dari tim pembuat soal bisa dicek di  Official Editorial Codeforces.


RINGKASAN SOAL

NN berselancar di media sosial dan selalu melihat suatu gambar yang terdiri dari sebuah lingkaran di tengah (inner circle) dan sejumlah $n$ lingkaran di luar (outer circle). Semua outer circle berukuran sama dengan jari-jari $R$ dan bersinggungan dengan inner circle yang memiliki jari-jari $r$. Gambar di atas merupakan contoh dua buah gambar yang pernah dilihat NN.

Bantu NN untuk menghitung jari-jari outer circle $R$, jika diketahui jari-jari inner circle $r$ dan jumlah outer circle $n$.

Input

Terdiri dari satu baris dengan dua angka terpisahkan oleh spasi. Masing-masing secara berurutan adalah nilai $n$ dan $r$ dimana $(3 \leq n \leq 100, 1 \leq n \leq 100)$, yakni jumlah outer circle dan jari-jari inner circle.

Output

Terdiri dari sebuah nilai $R$ — jari-jari outer circle yang dibutuhkan untuk membentuk gambar (agar semua outer circle) bersinggungan dengan inner circle. Jawaban diterima jika nilai error absolutnya tidak melebihi 10-6

Jika jawaban NN adalah $a$, dan jawaban juri adalah $b$, maka jawaban NN diterima jika dan hanya jika $\frac{\quad \lvert a-b\rvert \quad}{\max{(a, \lvert b\rvert)}} \le 10^{-6}$

Contoh dan pembahasan

input $n$ dan $r$:

output $R$:

Input di atas dapat diilustrasikan pada gambar di bawah ini. Setiap titik pusat dari outer circle jika dihubungkan dapat membentuk segi-$n$ sama sisi. Dikarenakan $n$ pada contoh ini adalah 3, maka yang terbentuk adalah segi tiga sama sisi $ABC$, di mana sisinya merupakan dua kali panjang jari-jari outer circle yakni sebesar $2R$. Kemudian, dari segitiga sama sisi tersebut dapat digambar lagi sebuah segitiga sama kaki $BCD$ (warna biru) untuk mencari nilai $R$.

Dari segitiga sama kaki $BCD$ di atas dapat dicari nilai $R$ dengan menerapkan salah satu rumus trigonometri:

Rumus trigonometri:
$\sin{\angle\text{BDt}} = \frac{\text{Bt}} {\text{BD}}$

Rumus mencari R:
$\sin{\angle\text{BDt}} = \frac{\text{R}} {\text{R+r}}$
$(\text{R}*\sin{\angle\text{BDt}}) + (\text{r}*\sin{\angle\text{BDt}}) = \text{R}$
$\text{R}*(\sin{\angle\text{BDt}} – 1) = -\text{r}*\sin{\angle\text{BDt}}$
$\text{R} = \frac{-\text{r} \; * \; \sin{\angle\text{BDt}}} {\sin{\angle\text{BDt}} \;- \;\text{1}}$
$\text{atau}$
$\text{R} = \frac{\text{r} \; * \; \sin{\angle\text{BDt}}} {\text{1} \;- \;\sin{\angle\text{BDt}}}$

Besar $\angle \text{BDC}$ diperoleh dari hasil bagi sudut lingkaran yakni $\text{360}^\circ$ dengan jumlah outer circle yakni $n$. Setelah diketahui besaran sudut, maka dengan menggunakan rumus di atas dapat dihitung nilai $R$. 

Nilai R:
$\angle \text{BDC} = \frac{360^\circ}{ \text{n}}$
$\angle \text{BDt} = \frac{\angle \text{BDC}}{\text{2}}$
$\angle \text{BDt} = \frac{120^\circ} {\text{2}} = 60^\circ$ 

$\text{R} = \frac{\text{1} \; * \; \sin{\text{60}^\circ}} {\text{1} \;- \;\sin{\text{60}^\circ}}$
$\text{R} = \frac{0.8660254}{0.1339745}$
$\text{R} = \text{6.46410161514}$

Belajar Machine Learning via StackExchange

Salah satu yang menantang menurut saya untuk belajar Artificial Intelligence/Machine Learning/Data Mining adalah untuk belajar saja, kadang kita perlu menuliskan sintaks kode yang lumayan panjang dan kompleks. Mulai dari merapikan data, preprocessing, feature extraction, sampai proses utamanya sendiri. Kadang hal ini yang bikin jadi down dulu sebelum memulai belajar, apalagi bagi kita yang kesulitan meluangkan banyak waktu untuk sekadar latihan.

Nah, salah satu solusi belajar yang saya temui cukup membantu saya adalah dengan aktif di ruang diskusi yang membahas Machine Learning di internet. Salah satu forum diskusi yang cukup baik menurut saya adalah forum-forum terbitan StackExchange, seperti Stackoverflow, CrossValidated, atau AIStackExchange. Bagi kita programmer, saya yakin nama-nama itu bukanlah nama yang asing. Walau bukan benar-benar “forum diskusi” (situs StackExchange adalah situs tanya jawab atau QA site) situs-situs tersebut cukup baik untuk digunakan sebagai sarana belajar.

Salah satu sisi positif yang saya rasakan dari aktif di StackExchange kita bisa belajar dengan memperdalam logika dan teori dengan waktu yang relatif lebih singkat, tanpa harus membuat kode yang cukup panjang.

Note: aktif di forum hanyalah salah satu alternatif bagi teman-teman yang kesulitan meluangkan waktu banyak tapi tetap ingin belajar. Namun, bagi teman-teman yang ingin serius mendalami bidang ini, saya tetap sangat menyarankan untuk meluangkan waktu khusus untuk belajar untuk menyelesaikan kasus-kasus dan coding dari scratch.

Belajar Machine Learning via StackExchange

Ada beberapa cara bagi yang ingin belajar machine learning via stackexchange. Bisa dengan cara membaca-baca pertanyaan yang telah dijawab, aktif bertanya, ataupun aktif menjawab.

Belajar dari Pertanyaan Orang Lain

Cobalah mencari pertanyaan yang setopik dengan materi yang ingin kalian perlajari. Telusuri satu persatu pertanyaan yang sudah pernah ditanyakan, siapa tahu kalian menemukan pertanyaan atau jawaban yang menarik yang sebenarnya cukup penting untuk ditanyakan tapi kita tidak pernah terpikirkan.

Seperti pertanyaan yang baru-baru ini saya temui: kenapa kita menggunakan istilah “Machine Learning”, bukan “Program Learning” atau Bisakah kita menggunakan Neural Network untuk mendeteksi suatu bilangan itu  prima atau bukan.

Dengan melihat jawaban orang lain kita juga jadi bisa menambah wawasan dengan menemukan solusi solusi menarik bagaimana orang menyelesaikan masalahnya.

Berani Bertanya

Tidak ada salahnya untuk bertanya asal dengan cara yang baik. Ada dua cara untuk kita bertanya di StackExchange, yang pertama kita bisa membuat pertanyaan baru, dan yang kedua adalah bertanya untuk meminta kejelasan jawaban via kolom komentar (ini butuh reputasi).

Untuk membuat pertanyaan baru, pastikan terlebih dahulu pertanyaan itu belum pernah ditanyakan sebelumnya. Untuk lebih yakin, cobalah googling kembali pertanyaan itu, atau bahkan lakukan parafrase jika perlu. Selain itu, pastikan juga kalian sudah membaca aturan singkat di halaman tour yang selalu ada di situs StackExchange manapun.

Contohnya di StackOverflow kalian akan mengenal istilah MVCE (Minimum Veriviable Complete Example), yakni sebuah aturan bagaimana memberikan contoh program kita yang eror secara minimalis. Secara tidak langsung, kita akan belajar bagaimana menjelaskan eror pada program kita secara baik kepada orang lain.

Note: Ingat, jika ingin mendapat jawaban yang baik, maka bertanyalah dengan cara baik.

Mencoba Memberi Jawaban

Selalu ada ilmu yang bisa kita bagi! Cobalah cari pertanyaan-pertanyaan sederhana yang sekiranya bisa kita jawab. Dengan mencoba menjawab beberapa pertanyaan, kita akan belajar untuk memahami lebih dalam materi yang kita pelajari. Kalau ada orang bilang, dengan mengajar ilmu kita bertambah, maka benar saja, dengan mencoba menjawab pertanyaan-pertanyaan di sana kita akan semakin bertambah wawasannya. Kita akan belajar bagaimana menjelaskan dan memberi contoh yang menjawab pertanyaan pengguna lain.

Takut di-downvote 🙁

Ketika memberi jawaban atau pertanyaan, tentunya kita akan mendapat beragam feedback entah dari pengguna lain atau dari si-penanya. Mulai dari komentar, flag, atau downvote. Jangan minder jika ada feedback negatif, toh, namanya juga belajar dan diskusi 🙂 Manusia tidak ada yang sempurna untuk luput dari kesalahan dan juga tidak semua manusia baik dan ramah untuk berdiskusi. Gunakan hal tersebut sebagai pengalaman untuk menjawab di kemudian hari.

Saya juga masih beberapa kali dapat komentar pedas atau “flag” pada pertanyaan saya karena tidak sesuai topik, tetapi bukan berarti lalu saya akan menghakimi forum tersebut tidak ramah dan melepas kesempatan saya belajar di sana.

Mulai Belajar!

Banyak pengalaman dan ilmu yang saya peroleh dengan aktif di StackExchange. Saya ingat bagaimana StackExchange telah membantu saya tidak hanya menyelesaikan skripsi saya, tetapi juga memahami lebih dalam tools yang saya gunakan. Selain itu semenjak aktif di StackExchange, saya juga merasa banyak terlatih untuk berkomunikasi dengan bahasa inggris secara natural. Jadi, Jangan ragu untuk memulai 😉 Semoga Bermanfaat!

Sumber gambar: Pexels

Template Curriculum Vitae untuk LaTeX

Beberapa waktu lalu saya penasaran dengan tampilan Curriculum Vitae / CV/ Resume yang baik. Di internet ada banyak tampilan dengan beragam format, tapi kali ini saya tertarik untuk membuat CV dengan LaTeX.

Pilihan pertama saya jatuh pada CV buatan Thomas Jansson. Templatenya (file resume.cls) bisa didownload langsung di halaman aslinya atau di daftar template Sharelatex.

Tampilan akhir CV dengan template oleh Thomas Jansson

Jika kalian perhatikan, desainnya sudah sangat baik, elegan, dan terkesan profesional. Cocok untuk CV para profesional yang panjang ataupun para freshgraduate yang belum banyak pengalaman. Hanya saja ada yang kurang menurut saya, yakni warna. Template aslinya hanya menghasilkan CV berwarna hitam putih.

Note: Bagian selanjutnya dari artikel ini akan menjelaskan pengalaman saya mengedit template LaTeX untuk menambahkan theme color pada template CV. Jika ingin langsung menggunakan template yang telah saya edit sehigga dapat berwarna, silakan download file resume.cls di repository berikut.

Mengedit LaTeX template

Berdasarkan banyak tips dalam pemberian warna di CV maka saya berusaha untuk tidak terlalu banyak mewarnai area CV, hanya meng-highlight bagian-bagian yang saya rasa penting untuk diberi warna, yakni teks judul dan teks subjudul pada sisi samping.

Untuk mengedit LaTeX template, kita akan mengedit file resume.cls yang tadi telah kita download. Pertama-tama, tambahkan package yang menyediakan pewarnaan teks pada bagian akhir:

Saya berikan parameter tambahan dvipsnames sehingga kita memperoleh lebih banyak pilihan warna yang memiliki “nama” (jadi tidak perlu menginputkan kode heksadesimal).

Selanjutnya utuk mempermudah penggunaan warna, saya membuat variabel yang menyimpan warna menggunakan perintah \colorlet:

Variabel themecolor adalah variabel yang akan kita gunakan untuk menyimpan warna template yang akan kita gunakan. Sedangkan MidnightBlue adalah warna tema yang saya gunakan untuk CV tersebut.

Note: Jika ingin mengganti warna template CV, ubah MidnightBlue menjadi warna lain sesuai selera

Selanjutnya kita cukup menyisipkan warna template kita ke bagian yang ingin kita beri warna, yakni judul dan subjudul di sisi samping. Di template, untuk mengedit kedua bagian tersebut kita dapat mengedit style yang digunakan, yakni mysidestyle dan mytitle.

Jika diperhatikan, di sini untuk mewarnai text saya menggunakan perintah textcolor{}. Sebenarnya ada dua cara yang dapat digunakan yakni dengan color{} atau textcolor{}, tetapi cara pertama akan membuat eror pada template (text tidak lagi teralinea dengan rapi)

Setelah selesai, template resume.cls sudah akan dapat memberikan warna pada bagian-bagian yang kita tentukan. Jika sebelumnya sudah pernah menggunakan template dari Thomas Janssen, perubahan ini seharusnya tidak akan mengubah apapun kecuali pemberian warna.

Hasil template CV dengan warna tema MidnightBlue

featured image credit: https://www.philippewiget.com


Meng-custom Perintah/Command di Terminal Ubuntu

Beberapa waktu lalu saya mendapat kesempatan untuk ikut Grand Final Kode Indonesia di Jakarta. Kode Indonesia adalah sebuah kontes pemrograman yang diadakan oleh Kalibrr.

Berbeda dengan kontes pemrograman pada umumnya, pada kontes ini panitia tidak menyediakan komputer atau laptop untuk para finalis. Jadi para finalis dipersilakan untuk menggunakan komputernya masing-masing di Grand Final. Sebenarnya ini peraturan yang aneh karena ini membuat setiap peserta bisa jadi punya “starting-point” yang berbeda kan? misal kualitas komputer, file-file yang tersedia, dsb.

Tapi ya sudah, karena ini aturan panitia sendiri maka saya juga mencoba menyiapkan laptop saya. Hal sederhana yang saya pikirkan adalah:

Meng-custom perintah atau command di terminal Ubuntu: Coba buat perintah sederhana untuk meng-compile sekaligus menjalankan program C++!

Tujuan command tersebut tentu untuk mempersingkat proses compile. Karena saya sendiri biasa tidak menggunakan IDE yang bisa meng-compile program, maka cara saya biasanya untuk meng-compile file C++ adalah dengan menjalankan perintah (command) berikut:

Lalu setelah di-compile, dijalankan dengan perintah:

Nah, misi sederhana saya saat itu adalah menyederhanakan kedua perintah di atas menjadi sebuah perintah sederhana. Setelah browsing-browsing, berikut ini rangkuman langkah-langkahnya:

  1. Buat sebuah script file, misalnya kita beri nama customcpp.sh
  2. Pada baris pertama, tuliskan #!/bin/bash lalu tuliskan perintah yang ingin dijalankan di bawahnya seperti di bawah. Pada perintah di bawah CPPFILE adalah variabel yang menyimpan argumen yang akan diinputkan saat pemanggilan. Nantinya akan menerima nama file yang akan di-compile.
  3. Simpan file tersebut, lalu pindahkan ke /usr/local/bin, pemindahannya bisa menggunakan command di bawah. SCRIPTNAME adalah nama perintah yang akan dipanggil ketika script di atas di jalankan.
  4. Atur permission agar program bisa diakses

Dan… selesai!

Setelah selesai, sekarang untuk mengcompile sekaligus menjalankan program C++, saya cukup mengetikkan di terminal command berikut ini:

ya.. setidaknya sedikit lebih cepat dari sebelumnya kan 😉

Sumber: