12. Greedy — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/12/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Bandingkan jalan pikiranmu dengan bagian Cara berpikir, bukan kodenya baris per baris: dua kode yang berbeda bentuk bisa sama-sama benar, dan yang perlu ditiru adalah cara sampai ke sana. Bagian Uji di tiap soal berisi masukan dan keluaran yang sudah diperiksa — jalankan jawabanmu sendiri dengan masukan itu sebelum merasa selesai.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/12/homework/solutions/01-kembalian.cpp
./jawab

Soal 1 — Uang kembalian

Soal. Lembar paling sedikit untuk membayar k dengan pecahan rupiah.

Cara berpikir. Greedy langsung: ambil sebanyak mungkin dari pecahan terbesar, sisanya diteruskan ke pecahan berikutnya. k / pecahan[i] memberi jumlah lembarnya dan k % pecahan[i] memberi sisanya — dua operasi yang sudah dikenal sejak Bab 03.

Greedy benar di sini karena setiap pecahan rupiah habis membagi pecahan di atasnya atau berkelipatan rapi (1.000 → 2.000 → 5.000 → 10.000 → …). Sifat itu yang membuat mengambil pecahan besar tidak pernah merugikan.

Pembahasan.

int pecahan[] = {100000, 50000, 20000, 10000, 5000, 2000, 1000};

long long lembar = 0;
for (int i = 0; i < 7; i++) {
    lembar += k / pecahan[i];
    k %= pecahan[i];
}
cout << lembar << "\n";

Uji.

Baris terakhir menguji tipe data: nilai k sampai 10⁹ masih muat di int, tetapi jawaban dan sisa perhitungannya lebih aman ditampung long long.

Kesalahan umum.

• Menulis pecahan tidak terurut menurun. Greedy langsung rusak.
• Memakai int untuk k sampai 10⁹ (masih muat) tetapi lupa bahwa jumlah lembarnya bisa besar juga — untuk k = 10⁹ jawabannya 10.000 lembar, masih aman, tetapi biasakan long long untuk penampung.

Soal 2 — Penjadwalan kegiatan

Soal. Kegiatan terbanyak yang bisa diikuti.

Cara berpikir. Urutkan menurut waktu selesai, lalu ambil setiap kegiatan yang mulainya tidak lebih awal dari selesainya kegiatan terakhir yang diambil. Alasannya: kegiatan yang selesai paling awal menyisakan waktu terbanyak untuk sisanya.

Nilai awal waktu harus lebih kecil dari semua waktu mulai yang mungkin, supaya kegiatan pertama pasti terambil.

Pembahasan.

sort(keg, keg + n, [](Kegiatan a, Kegiatan b) {
    return a.selesai < b.selesai;
});

int banyak = 0, waktu = -1000000000;
for (int i = 0; i < n; i++) {
    if (keg[i].mulai >= waktu) {
        banyak++;
        waktu = keg[i].selesai;
    }
}

Uji.

Kasus kedua adalah contoh penyangkal untuk greedy "waktu mulai paling awal", yang akan menjawab 1. Kalau jawabanmu 1 di sini, berarti ukuran pengurutannya masih salah. Kasus pertama menguji kegiatan berdurasi nol — ia tetap satu kegiatan yang sah.

Kesalahan umum.

• Mengurutkan dua array terpisah (mulai[] dan selesai[]), sehingga pasangannya rusak. Pakai struct.
• Memakai > alih-alih >=, sehingga kegiatan yang mulai tepat saat kegiatan lain selesai ikut ditolak — padahal soal mengizinkannya.

Soal 3 — Muatan perahu

Soal. Perahu paling sedikit, dua orang per perahu, total berat ≤ k.

Cara berpikir. Orang terberat pasti harus berangkat dengan suatu perahu. Pertanyaannya hanya: siapa yang bisa menemaninya? Kalau ada yang bisa, yang paling menguntungkan adalah yang paling ringan — karena kalau yang paling ringan pun tidak muat, tidak ada yang muat.

Dari situ muncul pola dua penunjuk: kanan selalu maju mundur satu langkah (orang terberat selalu berangkat), dan kiri hanya maju kalau ia ikut naik.

Pembahasan.

sort(b, b + n);

int kiri = 0, kanan = n - 1, perahu = 0;
while (kiri <= kanan) {
    if (b[kiri] + b[kanan] <= k) kiri++;
    kanan--;
    perahu++;
}

Uji.

Perhatikan bahwa keduanya berakhir dengan satu orang berangkat sendiri. Itu wajar: yang menentukan bukan banyaknya orang, melainkan apakah yang paling ringan masih muat bersama yang paling berat.

Kesalahan umum.

• Memasangkan dua orang teringan lebih dulu. Untuk 20 30 50 70 90 dengan k = 100, cara itu memberi 4 perahu, bukan 3.
• Menulis while (kiri < kanan), sehingga orang terakhir yang berangkat sendirian tidak pernah terhitung.

Soal 4 — Greedy yang gagal

Soal. Cari k yang membuat greedy salah untuk koin {1, 3, 4}.

Cara berpikir. Fungsi terbaik ditulis rekursif: untuk setiap koin yang muat, coba ambil koin itu dan selesaikan sisanya. Ini brute force, dan cukup cepat sampai k = 30. (Bab 13 memperbaikinya menjadi dynamic programming.)

Keluarannya.

k = 6:  greedy 3, terbaik 2
k = 10: greedy 4, terbaik 3
k = 14: greedy 5, terbaik 4
k = 18: greedy 6, terbaik 5
...

Polanya jelas: setiap k berbentuk 4m + 2 membuat greedy salah, karena greedy mengambil koin 4 sampai tersisa 2, lalu terpaksa memakai dua koin 1, padahal dua koin 3 lebih hemat.

Pembahasan.

int greedy(int k) {
    int jumlah = 0;
    for (int i = 0; i < 3; i++) { jumlah += k / koin[i]; k %= koin[i]; }
    return jumlah;
}

int terbaik(int k) {
    if (k == 0) return 0;
    int hasil = BESAR;
    for (int i = 0; i < 3; i++) {
        if (k >= koin[i]) {
            int calon = terbaik(k - koin[i]) + 1;
            if (calon < hasil) hasil = calon;
        }
    }
    return hasil;
}

Uji. Program jawabannya mencetak setiap k yang hasilnya berbeda:

k = 6: greedy 3, terbaik 2
k = 10: greedy 4, terbaik 3
k = 14: greedy 5, terbaik 4
k = 18: greedy 6, terbaik 5
k = 22: greedy 7, terbaik 6
k = 26: greedy 8, terbaik 7
k = 30: greedy 9, terbaik 8

Perhatikan polanya: kegagalan muncul setiap empat langkah, mulai dari 6. Yang layak direnungkan bukan polanya, melainkan kenyataan bahwa dari 30 nilai yang diuji, greedy benar pada 23 di antaranya. Penyelesaian yang benar 77 persen dari waktu tetap bernilai nol di penilai daring.

Kesalahan umum.

• Menyimpulkan "greedy selalu salah untuk soal koin". Yang benar: greedy bergantung pada himpunan koinnya.
• Menulis terbaik tanpa kasus dasar k == 0.

Tantangan — Ukuran pengurutan yang salah

Soal. Tunjukkan kegagalan greedy menurut waktu mulai dan menurut durasi.

Cara berpikir. Untuk ukuran pengurutan selain waktu selesai, penelusuran satu arah tidak cukup — setiap calon harus diperiksa terhadap semua kegiatan yang sudah diambil. Itu membuat perbandingannya adil: yang diuji adalah ukuran pengurutannya, bukan cara memeriksanya.

Pencari contoh penyangkal membangkitkan kegiatan acak dengan n antara 2 dan 5, lalu membandingkan tiap greedy dengan brute force atas semua 2ⁿ himpunan bagian.

Contoh penyangkal yang ditemukan.

Greedy menurut waktu mulai paling awal gagal pada lima kegiatan:

4 7   3 4   1 6   4 6   3 5

Greedy mengambil 1..6 lebih dulu, dan seluruh kegiatan lain bentrok dengannya — hasilnya 1. Jawaban terbaik 2, misalnya 3..4 bersama 4..7.

Greedy menurut durasi terpendek gagal pada empat kegiatan:

7 10   9 12   6 10   5 9

Durasi terpendek adalah 7..10, dan setelah diambil, semua sisanya bentrok — hasilnya 1. Jawaban terbaik 2: 5..9 bersama 9..12. Kegiatan pendek yang terletak persis di tengah bisa menabrak dua kegiatan sekaligus.

Sementara itu, greedy menurut waktu selesai tidak pernah salah pada 20.000 percobaan — sesuai dengan buktinya.

Kesalahan umum.

• Menguji dengan n besar. Contoh penyangkal yang ditemukan menjadi sulit dibaca; data kecil justru lebih berguna.
• Lupa menyalin ulang data sebelum memanggil greedy berikutnya. Setiap greedy mengurutkan array, sehingga urutan aslinya hilang dan perbandingannya tidak adil.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/12/osn/solutions/.

Soal 1 — Antrian Layanan

Cara berpikir. Perhatikan apa yang sebenarnya dihitung. Kalau urutannya sudah ditetapkan, pelanggan pertama menunggu 0, pelanggan kedua menunggu T pelanggan pertama, pelanggan ketiga menunggu jumlah dua yang pertama, dan seterusnya. Jadi layanan pelanggan yang dipanggil ke-i ikut dihitung sebanyak N − i kali di dalam total.

Dari situ jawabannya langsung terlihat: layanan yang paling lama sebaiknya dikalikan dengan angka sekecil mungkin, jadi ia dipanggil paling akhir. Urutkan naik.

Argumen penukaran. Ambil susunan terbaik mana pun. Andaikan ada dua pelanggan berdampingan dengan urutan x lalu y di mana x > y. Menukar keduanya tidak mengubah waktu tunggu pelanggan lain sama sekali — jumlah layanan sebelum mereka tetap, dan jumlah layanan setelah mereka juga tetap. Yang berubah hanya waktu tunggu mereka berdua: semula 0 dan x, menjadi 0 dan y, dan y < x. Jadi penukaran selalu memperbaiki atau menyamakan. Karena setiap susunan yang tidak urut naik pasti punya pasangan berdampingan seperti itu, susunan urut naik pasti termasuk yang terbaik.

Pembahasan.

sort(t.begin(), t.end());

long long berjalan = 0, total = 0;
for (int i = 0; i < n; i++) {
    total += berjalan;        // pelanggan ke-i menunggu selama ini
    berjalan += t[i];
}

cout << total << "\n";

Urutan dua baris di dalam perulangan menentukan jawabannya: waktu tunggu dicatat sebelum layanan pelanggan itu sendiri ditambahkan.

Batas atas totalnya: 10.000 × 200.000 × 199.999 / 2 ≈ 2 × 10¹⁴, jadi long long.

Uji.

Kesalahan umum.

• Menambahkan t[i] sebelum mencatat waktu tunggu, sehingga setiap pelanggan ikut menunggu dirinya sendiri.
• Mengurutkan turun.
• Memakai int untuk total.

Soal 2 — Titik Pemeriksaan

Cara berpikir. Godaannya adalah mengurutkan menurut ujung kiri. Itu salah: selang yang mulai lebih awal bisa jauh lebih panjang dan memberi sedikit sekali keterangan tentang di mana pos sebaiknya berdiri.

Kunci soal ini adalah ujung kanan. Urutkan selang menurut ujung kanannya. Ambil selang pertama yang belum terawasi, lalu dirikan pos tepat di ujung kanannya. Itu posisi terjauh ke kanan yang masih sah untuk selang tersebut, sehingga peluangnya mengawasi selang berikutnya paling besar. Tidak ada alasan menaruhnya lebih ke kiri.

Sesudah pos didirikan, selang berikutnya cukup diperiksa satu syarat: apakah pos terakhir masih berada di dalamnya, yaitu apakah titik ≥ Lᵢ. Ujung kanannya tidak perlu diperiksa, karena urutannya menjamin ujung kanan selang berikutnya tidak lebih kecil.

Pembahasan.

vector<pair<long long, long long>> selang(n);   // (kanan, kiri)
for (int i = 0; i < n; i++) {
    long long l, r;
    cin >> l >> r;
    selang[i] = {r, l};
}

sort(selang.begin(), selang.end());

int banyak = 0;
long long titik = -1;
for (int i = 0; i < n; i++) {
    long long kanan = selang[i].first;
    long long kiri = selang[i].second;

    if (banyak == 0 || titik < kiri) {
        banyak++;
        titik = kanan;
    }
}

Menyimpan pasangan sebagai (kanan, kiri) membuat sort biasa langsung mengurutkan menurut ujung kanan, tanpa perlu menulis fungsi pembanding.

Uji.

Kasus kedua adalah penguji urutan: kalau diurutkan menurut ujung kiri, selang 1 10 diproses lebih dulu dan posnya berdiri di kilometer 10, sehingga dua selang sisanya masing-masing perlu pos sendiri — jawabannya menjadi 3.

Kesalahan umum.

• Mengurutkan menurut ujung kiri.
• Menempatkan pos di tengah selang, atau di ujung kirinya.
• Memakai int untuk koordinat sampai 10⁹ — masih muat, tetapi titik = -1 sebagai nilai awal harus tetap lebih kecil daripada semua Lᵢ, jadi pemeriksaan banyak == 0 lebih aman daripada bergantung pada nilai awal.

Soal 3 — Pasangan Beban

Cara berpikir. Urutkan seluruh berat, lalu pasangkan yang terkecil dengan yang terbesar, terkecil kedua dengan terbesar kedua, dan seterusnya.

Argumen penukaran. Perhatikan barang terberat, sebut B. Ia pasti berpasangan dengan seseorang, dan beban gerobaknya adalah B ditambah berat pasangannya. Karena B tidak bisa dihindari, satu-satunya yang bisa dikecilkan adalah berat pasangannya — jadi pasangan terbaik untuk B adalah barang paling ringan. Sesudah keduanya diambil, sisanya adalah soal yang sama dengan 2(N − 1) barang, dan alasan yang sama berlaku lagi.

Pembahasan.

sort(a.begin(), a.end());

long long terbesar = 0;
for (int i = 0; i < n; i++) {
    long long jumlah = a[i] + a[2 * n - 1 - i];
    if (jumlah > terbesar) terbesar = jumlah;
}

cout << terbesar << "\n";

Perulangannya hanya sampai n, bukan 2 * n: setiap putaran sudah menangani dua barang sekaligus. Menulis 2 * n membuat setiap pasangan diperiksa dua kali — jawabannya kebetulan tetap benar, tetapi itu tanda bahwa struktur pasangannya belum dimengerti.

Uji.

Kesalahan umum.

• Memasangkan yang berdekatan setelah diurutkan — terkecil dengan terkecil kedua. Untuk contoh soal itu menghasilkan 13, bukan 9.
• Menjumlahkan seluruh beban lalu membaginya. Yang ditanya beban terberat, bukan rata-rata.
• Memakai int: dua berat 10⁹ berjumlah 2 × 10⁹, sudah melewati batas int.

Kalau masih tersendat

• Tidak tahu harus mengurutkan menurut apa → Bab 12, tabel ukuran pengurutan yang lazim.
• Greedy-mu benar untuk contoh tetapi salah di penilai → Bab 12, bagian Cara meyakinkan diri bahwa greedy benar.
• Data berpasangan berantakan sesudah diurutkan → Bab 12, catatan tentang struct.

Aturan yang tidak boleh dilanggar: uji dengan pembanding sebelum mengirim. Greedy yang belum diuji adalah cara tercepat kehilangan seluruh nilai satu soal.