TeachingCompetitive ProgrammingCP - Session 6
Week 6Workshop

CP - Session 6

Session 6 – Mathematics I: Panduan Contest

1. Akses Contest
Link https://vjudge.net/contest/858824
Access code / Password LA01-CP-006

Langkah

  1. Login ke Vjudge (buat akun jika belum punya).
  2. Buka link contest di atas.
  3. Masukkan access code LA01-CP-006 saat diminta.
  4. Pilih soal dari tab Problem, lalu submit solusi C++ kamu.
  5. Cek hasil di tab Status.

2. Daftar Soal

Label urutan di Vjudge mengikuti pengaturan contest, jadi cocokkan lewat judul soal.

Level Soal ID Codeforces Rating Topik
Easy Complicated GCD 664A 800 GCD, bilangan besar
Easy Almost Prime 26A 900 Prima, faktor
Easy-Medium T-primes 230B 1300 Sieve, teori bilangan
Easy-Medium Prime Matrix 271B 1300 Sieve, brute force
Challenging Orac and LCM 1349A 1600 GCD, LCM

3. Hints

Coba kerjakan sendiri dulu. Baca hint hanya jika buntu.

Complicated GCD (664A) Tulis rentang kecil, misalnya 4 sampai 7, lalu perhatikan dua bilangan paling awal di rentang itu: apa yang bisa kamu katakan tentang pembagi bersama mereka? Setelah itu, pikirkan apakah kamu benar-benar perlu menghitung sesuatu dengan angka sebesar 10^100.

Almost Prime (26A) Batas n kecil, jadi pendekatan sederhana per bilangan sudah cukup. Pikirkan cara menghitung faktor prima yang berbeda dari satu bilangan, dan apa yang terjadi kalau satu faktor dibagi habis dulu sebelum lanjut ke faktor berikutnya.

T-primes (230B) Tulis 4, 9, 25, 49 beserta daftar pembaginya dan cari kesamaannya. Lalu perhatikan: x bisa sampai 10^12, tetapi bilangan yang sebenarnya perlu diuji "prima" itu seberapa besar? Karena querynya banyak, siapkan sesuatu sekali di awal, dan hati-hati dengan sqrt pada tipe pecahan.

Prime Matrix (271B) Hitung dulu untuk setiap elemen, berapa langkah minimum agar ia menjadi prima (cukup sekali per elemen). Setelah itu, "matriks prima" tinggal soal memilih satu baris atau satu kolom, jadi pikirkan apa yang perlu dibandingkan. Pastikan juga tabel prima kamu cukup panjang, karena prima pertama setelah 10^5 mungkin lebih jauh dari perkiraanmu.

Orac and LCM (1349A) Ada sekitar n²/2 pasangan, jadi menghitung semuanya terlalu lambat. Cari hubungan antara gcd dan lcm: kalau satu bilangan a_i dibuat tetap sementara pasangannya berganti-ganti, apakah gcd dari banyak lcm(a_i, ...) bisa disederhanakan? Kamu mungkin butuh gcd dari "semua bilangan setelah posisi i", pikirkan cara menyiapkannya dalam satu kali jalan.

Selamat mengerjakan!