Babak Keseluruhan

Babak 1B Ngoding Seru 2019 diawali dengan soal Nilai Kelulusan, yang dapat diselesaikan dengan memperhatikan rentang kemungkinan nilai X. rais.fathin38 (Muhammad Rais Fathin Mudzakir) menjadi peserta pertama yang menyelesaikan seluruh soal pada babak ini pada menit ke-43.

Seluruh peserta yang mendapatkan peringkat 50 besar pada babak ini dapat mengikuti babak 2 pada 16 Maret, 7PM WIB. Kami akan mengirimkan e-mail kepada seluruh peserta yang lolos ke babak 2 sebagai konfirmasi.

Kepada seluruh peserta yang tidak berhasil lolos ke babak 2, kami menyarankan Anda mencoba lagi untuk mengikuti kesempatan Ngoding Seru berikutnya. Terima kasih kepada seluruh peserta Ngoding Seru 2019 atas partisipasinya.

Credits:

  • Nilai Kelulusan: Ditulis dan disiapkan oleh Jonathan Irvin Gunawan.
  • K FPB: Ditulis dan disiapkan oleh Muhammad Ayaz Dzulfikar.
  • Lampu Berwarna: Ditulis dan disiapkan oleh Jonathan Irvin Gunawan.
Solusi dan persiapan komponen soal lainnya dan juga review oleh Ashar Fuadi, Jonathan Irvin Gunawan, Muhammad Ayaz Dzulfikar, dan Wiwit Rifa'i.
Penulis analisis:

Nilai Kelulusan

Anggap himpunan nilai tidak lulus adalah gabungan nilai ulangan siswa kecuali ulangan terakhir untuk siswa tersebut. Dengan kata lain, himpunan nilai tidak lulus adalah gabungan Si, j untuk semua 1 ≤ i ≤ N, 1 ≤ j < Ui. Sebaliknya, anggap himpunan nilai lulus adalah gabungan nilai ulangan terakhir untuk setiap siswa. Dengan kata lain, himpunan nilai lulus adalah gabungan Si, Ui untuk semua 1 ≤ i ≤ N.

Nilai X yang dicari harus memenuhi dua syarat berikut ini:

  • X lebih besar dari semua elemen di himpunan nilai tidak lulus. Ini memastikan bahwa semua nilai di himpunan nilai tidak lulus memang tidak lulus.
  • X tidak lebih besar dari semua elemen di himpunan nilai lulus. Ini memastikan bahwa semua nilai di himpunan nilai lulus memang lulus.

Subsoal 1

Untuk subsoal ini, kita dapat menguji seluruh nilai dari 1 sampai 100. Kompleksitas solusi ini adalah 100 × O(Σ Ui).

Subsoal 2

Daripada menguji semua elemen pada himpunan nilai tidak lulus dan semua elemen pada himpunan nilai lulus, kita dapat mengambil hanya nilai maksimum pada himpunan nilai tidak lulus (anggap saja nilainya A) dan nilai minimum pada himpunan nilai lulus (anggap saja nilainya B). Nilai X yang dicari harus memenuhi A < X ≤ B. Jika A < B, maka kita dapat mengeluarkan nilai apapun di antara [A + 1, B]. Jika tidak, maka tidak terdapat nilai X yang mungkin. Kompleksitas solusi ini adalah O(Σ Ui).

K FPB

Subsoal 1

Untuk subsoal ini, kita dapat mencoba semua kemungkinan subhimpunan yang ada. Untuk setiap X subhimpunan dari S, kita periksa apakah FPB setiap pasang bilangannya adalah K. Jika iya, maka X merupakan kandidat solusi. Dari semua X yang merupakan kandidat solusi, ambil yang ukurannya paling besar.

Kompleksitas solusi ini adalah O(2N × N2 × log N) (mencari FPB memerlukan waktu O(log N)).

Subsoal 2

Perhatikan bahwa apabila X merupakan subhimpunan yang mana FPB setiap pasang anggotanya adalah K, maka untuk tiap 1 ≤ i ≤ |X|, Xi dapat dinyatakan dalam K × Yi untuk suatu Yi bilangan bulat positif, dan FPB(Yi, Yj) = 1 untuk tiap 1 ≤ i < j ≤ |X|. Untuk memaksimalkan ukuran X, kita cukup mengambil Yi berupa 1 dan semua bilangan prima pada rentang [1, N ⁄ K]. Buktinya cukup mudah: apabila terdapat Yi yang bukan bilangan prima, maka kita dapat memecahnya menjadi faktorisasi primanya, dan FPB tiap pasang akan tetap 1.

Kompleksitas solusi ini adalah O((N ⁄ K) log log (N ⁄ K)) untuk menghitung banyaknya bilangan prima pada rentang [1, N ⁄ K] menggunakan Sieve of Eratosthenes.

Lampu Berwarna

Untuk kemudahan berdiskusi, anggap L = KPK(|X|, |Y|) dan X' = X'0X'1...X'L - 1 dan Y' = Y'0Y'1...Y'L - 1 adalah string yang memenuhi X'i = Xi mod |X| dan Y'i = Yi mod |Y|, untuk semua 0 ≤ i < L. Dengan definisi X' dan Y' ini, pada detik ke-t (dari 0 sampai tak hingga), lampu A akan menyala dengan warna X't mod L dan lampu B akan menyala dengan warna Y't mod L.

Dapat diamati bahwa jika dan hanya jika kedua lampu ini menyala dengan warna yang berbeda pada detik ke-t, maka kedua lampu ini juga menyala dengan warna yang berbeda pada detik ke-(t + L). Ini berarti kita dapat mengamati kedua lampu hanya pada L detik pertama.

Jika kita definisikan himpunan Δ sebagai himpunan waktu i pada L detik pertama yang mana kedua lampu ini menyala dengan warna yang berbeda pada detik ke-i (dengan kata lain, Δ = {i | X'i ≠ Y'i, 0 ≤ i < L}), maka kedua lampu ini akan menyala dengan warna yang berbeda pada detik ke- (δ + j × L), untuk semua δ anggota dari Δ dan j bilangan bulat non-negatif. Kita dapat mengeluarkan K elemen terkecil dari bilangan-bilangan ini, atau K buah -1 jika Δ adalah himpunan kosong.

Subsoal 1

Untuk subsoal ini, kita dapat membuat string X' dan Y' pada memori dan menguji setiap indeks i pada rentang [0, L) untuk mencari Δ. Karena KPK(|X|, |Y|) dapat bernilai |X| × |Y| pada kasus terburuk, kompleksitas dari solusi ini adalah O(|X| × |Y| + K).

Subsoal 2

Without loss of generality, mari kita asumsikan bahwa |X| > |Y| untuk mempermudah diskusi. Mari kita definisikan LCP(i, j) (untuk 0 ≤ i < |X|, 0 ≤ j < |Y|) sebagai nilai terbesar k (0 ≤ k ≤ |Y| - j) yang memenuhi X(i + l) mod |X| = Yj + l untuk semua 0 ≤ l < k. Sebagai contoh, jika Xi ≠ Yj, maka LCP(i, j) = 0.

Anggap p = LCP(0, 0). Ini berarti X0X1...Xp - 1 = Y0Y1...Yp - 1. Terdapat dua kasus:

  • Jika p < |Y|, maka Xp ≠ Yp dan kita mendapatkan waktu pertama yang mana kedua lampu ini menyala dengan warna yang berbeda. Kita dapat melanjutkan pencarian waktu yang mana kedua lampu ini menyala dengan warna yang berbeda dengan memanggil LCP(p + 1, p + 1).
  • Jika p = |Y|, maka kita dapat mengetahui bahwa kedua lampu ini menyala dengan warna yang sama untuk |Y| detik pertama. Kita dapat melanjutkan pencarian waktu yang mana kedua lampu ini menyala dengan warna yang berbeda dengan memanggil LCP(|Y| mod |X|, 0).

Sehingga, dalam satu pemanggilan LCP, kita akan berhenti pada sebuah waktu yang mana kedua lampu ini menyala dengan warna yang berbeda, atau pada waktu yang merupakan detik ke-(z × |Y|) untuk sebuah bilangan bulat z. Pada rentang detik ke-[0, L), terdapat paling banyak |X| waktu yang merupakan detik ke-(z × |Y|) untuk sebuah bilangan bulat z, dan kita hanya ingin mencari K waktu pertama yang mana kedua lampu ini menyala dengan warna yang berbeda, sehingga kita hanya perlu melakukan paling banyak (K + |X|) pemanggilan LCP.

Untuk lebih jelasnya, algoritma ini dapat dilihat pada pseudocode berikut 

  Δ ← {}
  loop ← 0
  x ← 0
  while |Δ| < K:
    y ← 0
    while y < |Y|:
      lcp ← LCP(x + y, y)
      if y + lcp < |Y|:
        Δ ← Δ ∪ {loop × |Y| + y + lcp}
      y ← y + lcp + 1
    loop ← loop + 1
    x ← (x + |Y|) mod |X|
    if x = 0:
      break

Dengan menggunakan suffix array, satu pemanggilan LCP(i, j) dapat dihitung dalam O(log(|X| + |Y|)). Sehingga, total kompleksitas dari solusi ini adalah O((|X| + |Y| + K) × log(|X| + |Y|)).